Cod sursa(job #420477)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 19 martie 2010 14:12:34
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
//O(N^2*H)

#include<iostream>
#include<string>

using namespace std;

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

double X[NM],Y[NM];
int conv[NM];

char isin[NM];

int N;

double ab(double val)
{
     if(val>=0) return val;
     return -val;  
}

double ec(int p1,int p2,int p0)
{
     return (double)((DL)(X[p2]-X[p1])*(DL)(Y[p0]-Y[p1])-(DL)(X[p0]-X[p1])*(DL)(Y[p2]-Y[p1]));  
}

int all_on_one_side(int p1,int p2)
{
    int sign,i;
    
    for(i=1;i<=N;++i)
       if(i!=p1 && i!=p2)
       {
           int val=(int)ec(p1,p2,i);     
           sign=val/ab(val);     
           break;
       }
    
    for(;i<=N;++i)
       if(i!=p1 && i!=p2)
       {
           int val=(int)ec(p1,p2,i);     
           int nsign=val/ab(val);     
           if(nsign!=sign) return 0;
       }   
    
    return 1;   
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    
    scanf("%d",&N);
    
    for(int i=1;i<=N;++i)
       scanf("%lf %lf",&X[i],&Y[i]);
    
    X[0]=inf;
    
    conv[1]=0;
    
    for(int i=1;i<=N;++i)
    {
         double lx=X[conv[1]];
         double ly=Y[conv[1]]; 
         
         if(X[i]<lx || (X[i]==lx && Y[i]<ly)) conv[1]=i;
    }   
    
    int H=1;
    isin[conv[1]]=1;
    
    while(1)
    {
        int found=0;
        
        for(int i=1;i<=N;++i)
           if(!isin[i] && all_on_one_side(conv[H],i))
           {
               conv[++H]=i;
               isin[i]=1;
               found=1;
               break;        
           }    
       
        if(!found) break;    
    }
    
    printf("%d\n",H);
    
    for(int i=1;i<=H;++i)
       printf("%lf %lf\n",X[conv[i]],Y[conv[i]]);
    
    return 0;
}