Cod sursa(job #1689016)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 13 aprilie 2016 21:13:02
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>

#define NMax 120005
#define INF 0x3f3f3f3f
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct{
    double x,y;
}v[NMax],s[NMax];

int n,top,ind;

double unghi(punct A, punct B, punct C){
    return ((B.y - A.y) * (C.x - A.x) - (C.y - A.y)*(B.x - A.x));
}
bool cmp(punct x, punct y){
    return (unghi(v[1],x,y) > 0);
}

int main()
{
    f >> n;
    ind = 0;v[ind].x = INF; v[ind].y = INF;
    for(int i = 1; i <= n; ++i){
        f >> v[i].x >> v[i].y;
        if(v[ind].x == v[i].x && v[ind].y > v[ind].y){
            ind = i;
        }
        if(v[ind].x > v[i].x){
            ind = i;
        }
    }
    swap(v[ind],v[1]);
    sort(v + 2, v + 1 + n,cmp);
    s[++top] = v[1];
    s[++top] = v[2];
    for(int i = 3; i <= n; ++i){
        while(unghi(s[top - 1],s[top],v[i]) < 0){
            top--;
        }
        s[++top] = v[i];
    }
    g << top << '\n';
    for(int i = top; i >= 1; --i){
        g <<fixed<<setprecision(6)<< s[i].x << ' ' << s[i].y << '\n';
    }
    return 0;
}