Cod sursa(job #1142902)

Utilizator auRSTARHreapca Aurelian auRSTAR Data 14 martie 2014 13:20:23
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<deque>
using namespace std;
struct Punct{
    double x,y;
}P[120010];
bool cmp(Punct A,Punct B)
{
    long double det = 1LL*(P[1].x*A.y + A.x*B.y + P[1].y*B.x - A.y*B.x - P[1].x*B.y - P[1].y*A.x);
    return det>0;
}
bool trigo(int I,int J,int K)
{
    long double det = 1LL*(P[I].x*P[J].y + P[J].x*P[K].y + P[I].y*P[K].x - P[J].y*P[K].x - P[I].x*P[K].y - P[I].y*P[J].x);
    return det>0;
}
int ST[120010],head;
int i,n,pos;
double x,y;
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    scanf("%lf%lf",&x,&y);
    pos=1;
    P[1].x=x;P[1].y=y;
    for(i=2;i<=n;i++)
    {
        scanf("%lf%lf",&x,&y);
        if(P[pos].x==x && P[pos].y>y){ pos=i; }
        if(P[pos].x>x){ pos=i; }
        P[i].x=x;
        P[i].y=y;
    }
    if(pos!=1)swap(P[pos],P[1]);
    sort(P+2,P+n+1,cmp);
    ST[1]=1;
    ST[2]=2;
    head=2;
    for(i=3;i<=n;i++)
    {
        while(head>1)
        {
            if(trigo(ST[head-1],ST[head],i)==1)break;
            head--;
        }
        ST[++head]=i;
    }
    printf("%d\n",head);
    for(i=1;i<=head;i++)printf("%lf %lf\n",P[ST[i]].x,P[ST[i]].y);
}