Cod sursa(job #2536875)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 2 februarie 2020 19:14:04
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.08 kb
#include <bits/stdc++.h>

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> st;
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()
{
    st.push(0);
    used[0] = true;
    st.push(1);
    used[1] = true;
    for (int i = 2; i < n; ++i) {
        int k = st.top();
        st.pop();
        used[k] = false;
        while (orientation(pts[st.top()], pts[k], pts[i]) > 0) {
            k = st.top();
            st.pop();
            used[k] = false;
            if (st.empty())
                break;
        }
        st.push(k);
        st.push(i);
        used[k] = used[i] = true;
    }
    st.pop();
    used[n - 1] = used[0] = false;
    st.push(n - 1);
    st.push(n - 2);
    for (int i = n - 3; i >= 0; --i) {
        if (used[i] == true)
            continue;
        int k = st.top();
        st.pop();
        used[k] = false;
        while (orientation(pts[st.top()], pts[k], pts[i]) > 0) {
            k = st.top();
            st.pop();
            used[k] = false;
            if (st.empty())
                break;
        }
        st.push(k);
        st.push(i);
        used[k] = used[i] = true;
    }
}

void print()
{
    int nr{0};
    st.pop();
    fout << st.size() << '\n';
    while (!st.empty()) {
        int top = st.top();
        fout << setprecision(6) << fixed << pts[top].x << ' ' << pts[top].y << '\n';
        st.pop();
    }
}

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