Cod sursa(job #265615)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 24 februarie 2009 09:56:56
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <stdio.h>

double x[12001],y[12001];
int p[12001],k,s[12001],l;

int pivot(int i,int j)
{
int si=0,sj=-1,aux;
double ax;

while (i<j)
 {
	if ((double)(x[j]-x[1])*(y[i]-y[1]) < (double)(x[i]-x[1])*(y[j]-y[1]))
	{
	ax = x[i];x[i]=x[j];x[j]=ax;
	ax = y[i];y[i]=y[j];y[j]=ax;

	aux = -sj;
	sj = -si;
	si = aux;
	}
 i+=si;
 j+=sj;
 }
return i;
}

int semn(int x1,int x2,int x3,int y1,int y2,int y3)
{
return (x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))>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;

scanf("%d\n",&n);
k=1;
scanf("%lf %lf\n",&x[1],&y[1]);
p[1]=1;
for (i=2;i<=n;i++)
{
p[i]=i;
scanf("%lf %lf\n",&x[i],&y[i]);
if (x[i]<x[k]) k=i;
else if (x[i]==x[k] && y[i]<y[k]) k=i;
}

x[0]=x[k];x[k]=x[1];x[1]=x[0];
y[0]=y[k];y[k]=y[1];y[1]=y[0];

sort(2,n);
l=2;
s[1] = 1;
s[2] = 2;

for (i=3;i<=n;i++)
{
while ((l>=2) && (!semn(x[s[l]],x[s[l-1]],x[i],y[s[l]],y[s[l-1]],y[i]))) l--;
s[++l] = i;
}

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

return 0;
}