Cod sursa(job #2535653)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 1 februarie 2020 10:18:55
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.36 kb
#include <bits/stdc++.h>
#define dbl double

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int MAXN = 120010;

struct Point
{
    double x, y;
    bool operator<(const Point& other) const {
        if (x != other.x)
            return x < other.x;
        return y < other.y;
    }
};

stack<int> st1, st2, sol;
Point pts[MAXN];
bitset<MAXN> used;
int n;

void read()
{
    fin >> n;
    for (int i = 0; i < n; ++i) {
        fin >> pts[i].x >> pts[i].y;
    }
}

int orientation(Point A, Point B, Point C)
{
    double det = (A.x - C.x) * (B.y - C.y) - (A.y - C.y) * (B.x - C.x);
    if (det < 0)
        return -1;
    if (det > 0)
        return 1;
    return 0;
}

void hull()
{
    st1.push(0);
    used[0] = true;
    st1.push(1);
    used[1] = true;
    for (int i = 2; i < n; ++i) {
        int k = st1.top();
        st1.pop();
        used[k] = false;
        while (orientation(pts[st1.top()], pts[k], pts[i]) < 0) {
            k = st1.top();
            st1.pop();
            used[k] = false;
            if (st1.empty())
                break;
        }
        st1.push(k);
        st1.push(i);
        used[k] = used[i] = true;
    }
    used[n - 1] = used[0] = false;
    st2.push(n - 1);
    st2.push(n - 2);
    for (int i = n - 3; i >= 0; --i) {
        if (used[i] == true)
            continue;
        int k = st2.top();
        st2.pop();
        used[k] = false;
        while (orientation(pts[st2.top()], pts[k], pts[i]) < 0) {
            k = st2.top();
            st2.pop();
            used[k] = false;
            if (st2.empty())
                break;
        }
        st2.push(k);
        st2.push(i);
        used[k] = used[i] = true;
    }
}

void print()
{
    int nr{0};
    while (!st2.empty()) {
        int top = st2.top();
        sol.push(top);
        st2.pop();
        ++nr;
    }
    st1.pop();
    while (st1.size() > 1) {
        int top = st1.top();
        sol.push(top);
        st1.pop();
        ++nr;
    }
    fout << nr << '\n';
    while (!sol.empty()) {
        int top = sol.top();
        fout << setprecision(6) << fixed << pts[top].x << ' ' << pts[top].y << '\n';
        sol.pop();
    }
}

int main()
{
    read();
    sort(pts, pts + n);
    hull();
    print();
    return 0;
}