Cod sursa(job #239352)

Utilizator gh09chisinau gheorghita gh09 Data 4 ianuarie 2009 17:13:30
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.56 kb
# include <cstdio>
# include <math.h>
# include <cmath>
# include <algorithm>

using namespace std;

# define FIN "infasuratoare.in"
# define FOUT "infasuratoare.out"
# define min(a, b) (a < b ? a : b)
# define max(a, b) (a > b ? a : b)
# define sqr(a) (a * a)
# define MAXN 120005

struct trio
{
   double x, y, U;
} Pct[MAXN];

int N, jos;
int S[MAXN];
double phi = 4 * atan(1), MaxU, MinU = 180.0, x, y;

     double dist(trio A, trio B)
     {
         return sqrt(sqr((A.x-B.x))+sqr((A.y-B.y)));
     }

     int cmp(trio A, trio B)
     {
         if (A.U != B.U) return A.U < B.U;
         
         return dist(A, Pct[jos]) < dist(B, Pct[jos]);
     }
   
     void compute(int i)
     {
         double rap;
         
         if (Pct[i].x == Pct[jos].x) 
            {
               Pct[i].U = 90.0;
               return;
            }
         
         rap = abs((Pct[i].y-Pct[jos].y)/(Pct[i].x-Pct[jos].x));
         Pct[i].U = atan(rap) * 180 / phi;
         if (Pct[i].x < Pct[jos].x) Pct[i].U = 180.0 - Pct[i].U;
         
         MinU = min(MinU, Pct[i].U);
         MaxU = max(MaxU, Pct[i].U);
     }
     
     int main()
     {
         freopen(FIN,"r",stdin);
         freopen(FOUT,"w",stdout);
         
         scanf("%d",&N);
         
         for (int i = jos = 1; i <= N; ++i)
            {
               scanf("%lf %lf",&Pct[i].x, &Pct[i].y);
               if (Pct[i].y < Pct[jos].y) jos = i;
            }
         
         for (int i = 1; i <= N; ++i)
           if (i != jos) compute(i);
            
         sort(Pct + 1, Pct + N + 1, cmp);
         
         int ct = 1, i, ok;
         S[1] = 1;
         
         for (i = 2; Pct[i].U == MinU; ++i)
            S[++ct] = i;
         
         for (; Pct[i-1].U != MaxU; ++i)
            {
                ok = 1;
                while (ok)
                   {
                      x = (Pct[S[ct-1]].x-Pct[i].x)*(Pct[S[ct]].y-Pct[i].y);
                      y = (Pct[S[ct]].x-Pct[i].x)*(Pct[S[ct-1]].y-Pct[i].y);
                      if (x - y < 0) --ct;
                        else
                          {
                             ++ct;
                             ok = 0;
                          }
                   }
                S[ct] = i;
            }
         
         for (int j = N; j >= i; --j)
            S[++ct] = j;
            
         printf("%d\n",ct);
         for (int i = ct; i >= 1; --i)
            printf("%lf %lf\n",Pct[S[i]].x, Pct[S[i]].y);
         
         return 0;
     }