Cod sursa(job #2284512)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 17 noiembrie 2018 11:21:59
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point {
    double x, y;
};

point a[120003];
bool sel[120003];
int st[240006];
int N, k;
bool cmp(point a, point b) {
    if(a.x < b.x) return true;
    else if(a.x == b.x && a.y <= b.y) return true;
    return false;
}

long long determ(point a, point b, point c) {
    return a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
}
int main()
{
    f >> N;
    for(int i = 1; i <= N; i++) {
        f >> a[i].x >> a[i].y;
    }
    sort(a + 1, a + N + 1, cmp);
    st[++k] = 1;
    st[++k] = 2;
    sel[2] = true;
    for(int i = 3; i <= N; i++) {
        while(k > 1 && determ(a[st[k - 1]], a[st[k]], a[i]) >= 0) {
            sel[st[k]] = false;
            st[k--] = 0;
        }
        st[++k] = i;
        sel[i] = true;

    }

    for(int i = N; i >= 1; i--) {
        if(!sel[i]) {
            while(k > 1 && determ(a[st[k - 1]], a[st[k]], a[i]) >= 0) {
                sel[st[k]] = false;
                st[k--] = 0;
            }
            st[++k] = i;
            sel[i] = true;
        }

    }
    g << k - 1 << setprecision(6) << fixed << "\n";
    for(int i = k - 1; i >= 1; i--) {
        g << a[st[i]].x << " " << a[st[i]].y << "\n";
    }
    return 0;
}