Cod sursa(job #303515)

Utilizator EcthorIorga Dan Ecthor Data 9 aprilie 2009 22:01:56
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
 #include<stdio.h>  
 #include<algorithm>  
 #include<math.h>  
   
 using namespace std;  
   
 const int maxn = 120000;  
 const int INF = 1000000000;  
   
 double X[maxn],Y[maxn];  
 long double V[maxn];  
 int PI,IND[maxn],N,ST[maxn];  
   
 bool cmpf(int i,int j)  
 {  
     return (double)(X[i] - X[PI]) * (Y[j] - Y[PI]) < (double)(X[j] - X[PI]) * (Y[i] - Y[PI]);  
 }  
   
 long double semn(int i1,int i2,int i3)  
 {  
     return (long double)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()  
 {  
     freopen("infasuratoare.in","r",stdin);  
     freopen("infasuratoare.out","w",stdout);  
     scanf("%d\n",&N);  
     X[0] = INF;Y[0] = INF;  
     int punct_initial = 0;  
     for(int i = 1;i <= N; ++i)  
     {  
         scanf("%lf %lf",&X[i],&Y[i]);  
         if (X[i] < X[punct_initial] || (X[i] == X[punct_initial] && Y[i] < Y[punct_initial])) punct_initial = i;  
     }  
     PI = punct_initial;  
     for(int i = 1;i <= N; ++i)  
     {  
         if (i == punct_initial) continue;   
         IND[++IND[0]] = i;  
     }  
     sort(IND + 1,IND + IND[0] + 1,cmpf);  
     ST[ST[0] = 1] = punct_initial;  
     for(int i = 1;i <= IND[0]; ++i)  
     {  
         if (IND[i] == punct_initial) continue;  
         while(ST[0] >= 2 && semn(ST[ST[0] - 1],ST[ST[0]],IND[i]) > 0) --ST[0];  
         ST[++ST[0]] = IND[i];  
     }  
     ST[++ST[0]] = punct_initial;  
     printf("%d\n",ST[0] - 1);  
     reverse(ST + 1, ST + ST[0] + 1);  
     for(int i = 1;i < ST[0]; ++i)  
     {  
         printf("%lf %lf\n",X[ST[i]],Y[ST[i]]);  
     }  
     return 0;  
}