Cod sursa(job #430973)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 31 martie 2010 15:09:13
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

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

double X[NM],Y[NM];

int N,PI,P[NM],STK[NM];

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

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

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