Cod sursa(job #266263)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 25 februarie 2009 09:55:15
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <stdio.h>
#define nmax 120001

struct p{double x,y;};

p A[nmax];
int st[nmax],l;


int pivot(int st,int dr)
{
int s0=0,d0=-1,aux;

while (st<dr)
{
if ((double)(A[dr].x-A[1].x)*(A[st].y-A[1].y) < (double)(A[st].x-A[1].x)*(A[dr].y-A[1].y))
   {
    A[0] = A[dr];
    A[dr] = A[st];
    A[st] = A[0];

    aux = -s0;
    s0 = -d0;
    d0 = aux;
   }
st+=s0;
dr+=d0;
}
return st;
}

int cmp(p A,p B, p C)
{
double s = (A.x-C.x)*(B.y-C.y)-(A.y-C.y)*(B.x-C.x);
if (s<0) return 1;
return 0;
}


void sort(int st,int dr)
{
if (st<dr)
{
int m = pivot(st,dr);
sort(st,m-1);
sort(m+1,dr);
}
}


int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);


int n,i,k;

scanf("%d\n",&n);

scanf("%lf %lf \n",&A[1].x,&A[1].y);
k=1;

for (i=2;i<=n;i++)
{
scanf("%lf %lf \n",&A[i].x,&A[i].y);
//printf("%lf %lf \n",A[i].x,A[i].y);
if (A[i].x<A[k].x) k=i;
else if ((A[i].x==A[k].x && A[i].y<A[i].y)) k=i;
}


A[0] = A[1];
A[1] = A[k];
A[k] = A[0];

sort(2,n);

l=1;
st[l]=1;

for (i=2;i<=n;i++)
{
while (l>=2 && cmp(A[st[l]],A[st[l-1]],A[i])) l--;
st[++l]=i;
}

printf("%d\n",l);
while (l)
{
printf("%lf %lf\n",A[st[l]].x,A[st[l]].y);
l--;
}

return 0;
}