Cod sursa(job #411953)

Utilizator aghamatMorariu Razvan aghamat Data 5 martie 2010 11:39:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include <stdio.h>

#define Nmax 220100

struct P { double x,y; };

P a[Nmax];
int st[Nmax], vf, n;

inline int cmp_(P a, P b)
{
     if (a.y > b.y) return 1;
     if (a.y < b.y) return -1;
     if (a.x > b.x) return 1;
     if (a.x < b.x) return -1;
     return 0;          
}

inline int sens(P A,P B, P C)
{
     double semn = ((B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x));
     if (semn < 0) return -1;
     if (semn > 0) return 1;
     return 0;     
}

inline int cmp(P A,P B)
{     
     return sens(a[1],A,B);             
}

void sort(int st,int dr)
{
     int i=st,j=dr;
     P sch=a[(i+j)/2], tmp;
     do {
          while (cmp(a[i],sch) == 1) ++i;
          while (cmp(sch,a[j]) == 1) --j;
          if (i<=j)
          {
               tmp = a[i];
               a[i] = a[j];
               a[j] = tmp;
               ++i; --j;     
          }
     } while (i<=j);
     if (st<j) sort(st,j);
     if (i<dr) sort(i,dr);
}

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", &a[i].x, &a[i].y);
          
     for (int i=2;i<=n;++i)
          if (cmp_(a[1],a[i])==1)
          {
               a[0] = a[1];
               a[1] = a[i];
               a[i] = a[0];     
          }
     
     sort(2,n);
          
     st[++vf] = 1;
     
     for (int i=2;i<=n;++i)
     {
          while (vf > 1 && sens(a[st[vf-1]],a[st[vf]],a[i]) == -1)
               --vf;
          st[++vf] = i;     
     }
     while (vf > 1 && sens(a[st[vf]],a[st[vf]],a[1]) == -1)  --vf;
     
     printf("%d\n", vf);
     
     for (int i=1;i<=vf;++i)
          printf("%.6f %.6f\n", a[st[i]].x, a[st[i]].y);         
     
     return 0;
}