Cod sursa(job #420504)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 19 martie 2010 16:03:04
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

#define NM 120005
#define DL long double
#define inf 2000000000

double X[NM],Y[NM];

int GP,ST[NM],P[NM];

bool cmpu(int i,int j)
{
     return (double)(Y[i]-Y[GP])*(X[j]-X[GP])<(double)(Y[j]-Y[GP])*(X[i]-X[GP]);
}

DL semn(int i1,int i2,int i3)
{
     return (DL)X[i1] * Y[i2] + X[i2] * Y[i3] + X[i3] * Y[i1] - Y[i1] * X[i2] - Y[i2] * X[i3] - Y[i3] * X[i1];       
}


int main()
{
    int N; 
    
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    
    scanf("%d",&N);
    
    X[0]=inf,Y[0]=inf;
    
    for(int i=1;i<=N;++i)
    {
        scanf("%lf %lf",&X[i],&Y[i]);
        
        if(X[i]<X[GP] || (X[i]==X[GP] && Y[i]<Y[GP])) GP=i;    
    }   
    
    for(int i=1;i<=N;++i)
       if(i!=GP) P[++P[0]]=i;
    
    sort(P+1,P+P[0]+1,cmpu);   
    
    ST[++ST[0]]=GP;
    
    /*
    for(int i=1;i<=P[0];++i)
       printf("%d ",P[i]);
    */
    
    for(int i=1;i<=P[0];++i)
    {
        while(ST[0]>2 && semn(ST[ST[0]-1],ST[ST[0]],P[i])<0) --ST[0];
        ST[++ST[0]]=P[i];    
    }
    
    printf("%d\n",ST[0]);
    
    for(int i=1;i<=ST[0];++i)
       printf("%lf %lf\n",X[ST[i]],Y[ST[i]]);
    
    return 0;
}