Cod sursa(job #1915387)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 8 martie 2017 20:52:02
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

const int NMax = 120005;
const int INF = 0x3f3f3f3f;

struct point{
    double x,y;
};

point a[NMax],s[NMax];
int n,ind,top;
double mn = INF;

double unghi(point A, point B, point C){
    return ((B.y - A.y) * (C.x - A.x) - (C.y - A.y) * (B.x - A.x));
}
bool cmp(point x, point y){
    return (unghi(a[1],x,y) > 0);
}
int main()
{
    f >> n;
    for(int i = 1; i <= n; ++i){
        f >> a[i].x >> a[i].y;
        if(a[i].x < mn){
            mn = a[i].x;
            ind = i;
        }
    }
    swap(a[1],a[ind]);
    sort(a + 2, a + 1 + n,cmp);
    s[++top] = a[1];
    s[++top] = a[2];
    for(int i = 3; i <= n; ++i){
        while(unghi(s[top - 1], s[top], a[i]) < 0){
            top--;
        }
        s[++top] = a[i];
    }
    g << top << '\n';
    for(int i = top; i >= 1; --i){
        g << fixed << setprecision(6) << s[i].x << ' ' << s[i].y << '\n';
    }
    return 0;
}