Cod sursa(job #1548008)

Utilizator madalindobrilaMadalin Dobrila madalindobrila Data 10 decembrie 2015 11:19:46
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point
{
    double x;
    double y;
}
P[120001],first,S[120001];
int pos,top,N;
double det(point p1, point p2, point p3)
{
    return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}
int cmp(point p1,point p2)
{
    return det(P[1],p1,p2)>0;
}
int main()
{
    f>>N;
    f>>P[1].x>>P[1].y;
    first=P[1];
    pos=1;
    for(int i=2;i<=N;i++){
        f>>P[i].x>>P[i].y;
        if(P[i].y<first.y || (P[i].y==first.y && P[i].x<first.x))
            first=P[i],pos=i;
    }
    swap(P[1],P[pos]);
    sort(P+2,P+N+1,cmp);
    S[1]=P[1];
    S[2]=P[2];
    top=2;
    for(int i=3;i<=N;i++){
        while(top>=2 && det(S[top-1],S[top],P[i])<0)
            top--;
        S[++top]=P[i];
    }
    g<<top<<endl;
    for(int i=1;i<=top;i++)
        g<<setprecision(6)<<fixed<<S[i].x<<" "<<setprecision(6)<<fixed<<S[i].y<<endl;
}