Cod sursa(job #995423)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 8 septembrie 2013 21:07:47
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<cstdio>
#include<algorithm>

#define Point pair<double,double>
#define x first
#define y second

using namespace std;
const int NMAX = 120005;
int N,i,Min,Cnt;
Point P[NMAX],St[NMAX];

int CrossProduct(const Point &A,const Point &B,const Point &C)
{
    double Ar=(B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
    if(Ar>0) return 1;
    if(Ar<0) return -1;
    return 0;
}

bool cmp(const Point &A,const Point &B)
{
    return CrossProduct(P[1],A,B)<0;
}

void Read()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&N); Min=1;
    for(i=1;i<=N;i++)
    {
        scanf("%lf",&P[i].x);
        scanf("%lf",&P[i].y);
        if(P[i]<P[Min]) Min=i;
    }
}

void Sort()
{
    swap(P[Min],P[1]);
    sort(P+2,P+N+1,cmp);
}

void ConvexHull()
{
    for(i=1;i<=N;i++)
    {
        while(Cnt>=2 && CrossProduct(St[Cnt-1],St[Cnt],P[i])>0) Cnt--;
        St[++Cnt]=P[i];
    }
}

void Write()
{
    printf("%d\n",Cnt);
    for(i=Cnt;i;i--) printf("%lf %lf\n",St[i].x,St[i].y);
}

int main()
{
    Read();
    Sort();
    ConvexHull();
    Write();
    return 0;
}