Cod sursa(job #1863790)

Utilizator cubaLuceafarul cuba Data 31 ianuarie 2017 10:50:14
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int nMax = 120003;
const double eps = 1e-12;
struct Point {
    double x, y;
};
inline bool cmp(const Point A, const Point B) {
    return A.y < B.y;
}
Point a[nMax];
bool viz[nMax];
int St[nMax];
inline double Semn(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;
    viz[2] = 1;
    St[++top] = 1;
    St[++top] = 2;
    int semn = 1;
    for(int i = 3; i ; i += semn) {
        if(!viz[i]) {
            while(top >= 2 && Semn(St[top - 1], St[top], i) < eps) {
                viz[St[top]] = 0;
                top--;
            }
            St[++top] = i;
            viz[i] = 1;
        }
        if(i == n) {
            semn = -1;
        }
    }
    g << top - 1 << "\n";
    for(int i = 2; i <= top; i++) {
        g <<  fixed << a[St[i]].x << " " << a[St[i]].y << setprecision(6) << "\n";
    }
    return 0;
}