Cod sursa(job #250804)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 31 ianuarie 2009 21:21:39
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
# include <cstdio>
# include <algorithm>

using namespace std;

# define FIN "infasuratoare.in"
# define FOUT "infasuratoare.out"
# define MAXN 120005

struct punct
{
   double x, y;
} P[MAXN];

int N, i, p, vf;
int St[MAXN];

     void swap(int i, int j)
     {
         punct aux;
         
         aux = P[i]; P[i] = P[j]; P[j] = aux;
     }
     
     int cmp(punct A, punct B)
     {
         return (double) (A.x-P[1].x)*(B.y-P[1].y) > (double) (B.x-P[1].x)*(A.y-P[1].y);
     }
     
     int sign(int i, int j, int k)
     {
         double x1, y1;
         
         x1 = (P[i].x - P[k].x) * (P[j].y - P[k].y);
         y1 = (P[j].x - P[k].x) * (P[i].y - P[k].y);
         
         if (x1 - y1 > 0) return 1;
         return -1;
     }
     
     int main()
     {
         freopen(FIN,"r",stdin);
         freopen(FOUT,"w",stdout);
         
         scanf("%d",&N);
         for (i = 1, p = 1; i <= N; ++i)
         {
             scanf("%lf %lf",&P[i].x ,&P[i].y);
             if (P[i].x < P[p].x) p = i;
             if (P[i].x ==P[p].x && P[i].y < P[p].y) p = i;
         }
         
         swap(1,p);
         
         sort(P + 2, P + N + 1, cmp);
         
         St[vf = 1] = 1;
         for (i = 2; i <= N; ++i)
         {
             while (vf >= 2 && sign(St[vf-1], St[vf], i) < 0) --vf;
             St[++vf] = i;
         }
         
         printf("%d\n",vf);
         for (i = 1; i <= vf; ++i)
           printf("%lf %lf\n",P[St[i]].x, P[St[i]].y);
         
         return 0;
     }