Cod sursa(job #1132968)

Utilizator alex_bucevschiBucevschi Alexandru alex_bucevschi Data 4 martie 2014 10:44:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstdio>
#include <utility>
#include <algorithm>
#define N 120010
#define punct pair<double,double>
#define X first
#define Y second
using namespace std;
punct P[N],Q[N];
int n,i,p,u,crit(punct,punct);
double x,y,det(punct,punct,punct);
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%lf%lf",&x,&y);
        P[i]=make_pair(x,y);
        if(P[i]<P[0]){punct U=P[0];P[0]=P[i];P[i]=U;}
    }
    sort(P+1,P+n,crit);
    Q[0]=P[0];Q[1]=P[1];p=0;u=1;
    for(i=2;i<n;i++)
    {
        while(det(Q[p],Q[u],P[i])<0){p--;u--;}
        p++;u++;Q[u]=P[i];
    }
    u++;
    printf("%d\n",u);
    for(i=0;i<u;i++)
        printf("%.6lf %.6lf\n",Q[i].X,Q[i].Y);
    return 0;
}
double det(punct A,punct B,punct C)
{
    return A.X*B.Y+B.X*C.Y+C.X*A.Y-A.Y*B.X-B.Y*C.X-C.Y*A.X;
}
int crit(punct A,punct B)
{
    double D=det(P[0],A,B);
    if(D>0)return 1;
    return 0;
}