Cod sursa(job #326473)

Utilizator IoannaPandele Ioana Ioanna Data 25 iunie 2009 12:20:51
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
#include<stdio.h>
#include<math.h>
#define eps 0.000000000001
#define nmax 120010
long n,w;
typedef struct {long double x,y;}point;
point p[nmax],ll,st[nmax];

void read()
{
scanf("%ld",&n);
long i,w;
w=1;
scanf("%Lf%Lf",&p[1].x,&p[1].y);
ll=p[1];
for (i=2;i<=n;i++)
    {
     scanf("%Lf%Lf",&p[i].x,&p[i].y);
     if ((p[i].y-ll.y)<(-1)*eps)
        {
         ll=p[i];
         w=i;
        }
     else if (fabs(p[i].y-ll.y)<=eps)
             {
              if ((p[i].x-ll.x)<(-1)*eps)
                 {
                  ll=p[i];
                  w=i;}
             }
    }
point aux;
aux=p[1];
p[1]=p[w];
p[w]=aux;
}

long cp(point p1,point p2,point p3)
{
long double p;
p=(p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
if (p<(-1)*eps)
    return -1;
if (p>eps)
    return 1;
return 0;
}

long double dist(point p1,point p2)
{
return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}


long part(long st,long dr)
{
long i,j,s;
point piv,aux;
i=st-1;
j=dr+1;
piv=p[(st+dr)/2];
while (1)
      {
       do {i++;s=cp(p[1],p[i],piv);}while (s>0 || (s==0 && dist(p[1],piv)>dist(p[1],p[i])));
       do {j--;s=cp(p[1],piv,p[j]);}while (s>0 || (s==0 && dist(p[1],p[j])>dist(p[1],piv)));
       if (i<j)
          {
           aux=p[i];
           p[i]=p[j];
           p[j]=aux;
          }
      else return j;
      }
}


void quicks(long st,long dr)
{
long p;
if (st<dr)
   {
    p=part(st,dr);
    quicks(st,p);
    quicks(p+1,dr);
   }
}


void convex()
{
long i;
st[1]=p[1];
w=2;
st[w]=p[2];
for (i=3;i<=n;i++)
    {
     while (w>2 && cp(st[w-1],st[w],p[i])<0)
           {
            w--;
           }
     st[++w]=p[i];
    }
while (w>2 && cp(st[w-1],st[w],p[1])<0)
      {
       w--;
      }
}

void print()
{
long i;
printf("%ld\n",w);
for (i=1;i<=w;i++)
    {
     printf("%Lf %Lf\n",st[i].x,st[i].y);
    }
}


int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
read();
quicks(2,n);
convex();
print();
return 0;
}