Cod sursa(job #303513)

Utilizator EcthorIorga Dan Ecthor Data 9 aprilie 2009 22:00:21
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
 #include<stdio.h>  
 #include<vector>  
 #include<math.h>  
 #include <algorithm>  
 #define pb push_back  
   
 const int maxn = 120000;  
   
 using namespace std;  
   
 vector<int> VECT;  
 double X[maxn],Y[maxn];  
 int N,VER[maxn];  
   
 int main()  
 {  
     freopen("infasuratoare.in","r",stdin);  
     freopen("infasuratoare.out","w",stdout);  
     scanf("%d\n",&N);  
     X[0] = 1000000000;Y[0] = 1000000000;  
     for(int i = 1;i <= N; ++i)  
         scanf("%lf %lf\n",&X[i],&Y[i]);  
     int punct_initial = 0;  
     int cur = 0;  
     int move = 1;  
     for(int i = 1;i <= N; ++i)  
         if (X[i] < X[punct_initial]) punct_initial = i;  
     cur = punct_initial;  
     double last = 0;  
     while(move || punct_initial != cur)  
     {  
         move = 0;  
         VECT.pb(cur);  
         double ma = 10000;  
         int poznoua = cur;  
         for(int i = 1;i <= N; ++i)  
         {  
             if (VER[i] || i == cur) continue;  
            double unghi = atan2((X[i] - X[cur]),Y[i] - Y[cur]);  
             if (unghi < 0) unghi += 2* M_PI;  
             unghi -= last;  
             if (unghi < 0) unghi += 2 * M_PI;  
             if (ma > unghi) {ma = unghi; poznoua = i;}  
         }  
         last = atan2(-(X[cur] - X[poznoua]),-(Y[cur] - Y[poznoua]));  
         if (last < 0) last += 2 * M_PI;  
         cur = poznoua;  
         VER[cur] = 1;  
     }  
    reverse(VECT.begin(),VECT.end());  
     printf("%d\n",VECT.size());  
     for(unsigned int i = 0;i < VECT.size(); ++i)  
         printf("%lf %lf\n",X[VECT[i]],Y[VECT[i]]);  
    return 0;  
 }