Cod sursa(job #2173772)

Utilizator cubaLuceafarul cuba Data 16 martie 2018 00:41:52
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int nMax = 120005;
const double eps = 1e-12;
struct Pct{
    double x, y;
};
inline bool cmp (const Pct &A, const Pct &B) {
    return A.y < B.y;
}
Pct a[nMax];
int St[nMax];
bool viz[nMax];
inline double Check(int i, int j, int k) {
    return (a[j].x-a[i].x)*(a[k].y-a[i].y)-(a[j].y-a[i].y)*(a[k].x-a[i].x);
}
int main()
{
    int n;
    f >> n;
    for(int i = 1; i <= n; i++) {
        f >> a[i].x >> a[i].y;
    }
    sort(a + 1, a + n + 1, cmp);
    int top = 0;
    St[++top] = 1;
    St[++top] = 2;
    viz[2] = 1;
    int semn = 1;
    for(int i = 3; i; i += semn) {
        if(!viz[i]) {
            while(top >= 2 && Check(St[top - 1], St[top], i) < eps) { ///le scot pe alea knn
                viz[St[top]] = 0;
                top--;
            }
            St[++top] = i;
            viz[i] = 1;
        }
        if(i == n) {
            semn = -1;
        }
    }
    g << top - 1 << "\n";
    for(int i = 1; i < top; i++){
        g <<  fixed << a[St[i]].x << " " << a[St[i]].y << setprecision(6) << "\n";
    }
    return 0;
}