Cod sursa(job #2521543)

Utilizator vxpsnVictor Pusnei vxpsn Data 11 ianuarie 2020 02:43:29
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int maxn = 120005;
const double ZERO = 1e-12;

struct point {
    double x, y;
    bool operator < (point t) const {
        return (x < t.x) || (x == t.x && y < t.y);
    }
};

int n, s[maxn], top;
bitset<maxn> in;
point a[maxn];

double crossProduct(point o, point a, point b) {
    return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}

int main() {
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> a[i].x >> a[i].y;

    sort(a + 1, a + n + 1);

    in[2] = 1;
    s[++top] = 1;
    s[++top] = 2;

    for(int i = 1; i <= n; ++i) {
        if(in[i] == 1) continue;
        while(top >= 2 && crossProduct(a[s[top - 1]], a[s[top]], a[i]) < ZERO) {
            in[s[top]] = 0;
            --top;
        }
        s[++top] = i;
        in[i] = 1;
    }
    for(int i = n - 1; i >= 1; --i) {
        if(in[i] == 1) continue;
        while(top >= 2 && crossProduct(a[s[top - 1]], a[s[top]], a[i]) < ZERO) {
            in[s[top]] = 0;
            --top;
        }
        s[++top] = i;
        in[i] = 1;
    }

    fout << fixed;
    fout << top - 1 << "\n";

    for(int i = 1; i < top; ++i)
        fout << setprecision(6) << a[s[i]].x << " " << a[s[i]].y << "\n";

    return 0;
}