Cod sursa(job #625720)

Utilizator matemariaescuMaria Mateescu matemariaescu Data 25 octombrie 2011 13:03:44
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
# include <stdio.h> 
# include <math.h>
# define abs(x) x>0?x:(-x)

int max,n,i,pct;
double aux[2];
int pol[100];
double p[100][2];

double dot(double A[], double B[], double C[])
{
    double AB[2];
    double BC[2];
    AB[0] = B[0]-A[0];
    AB[1] = B[1]-A[1];
    BC[0] = C[0]-B[0];
    BC[1] = C[1]-B[1];
    double d = AB[0] * BC[0] + AB[1] * BC[1];
    return d;
}

double cross(double A[], double B[], double C[])
{
    double AB[2];
    double AC[2];
    AB[0] = B[0]-A[0];
    AB[1] = B[1]-A[1];
    AC[0] = C[0]-A[0];
    AC[1] = C[1]-A[1];
    double c = AB[0] * AC[1] - AB[1] * AC[0];
    return c;
}

int aranjare (int st, int dr);
void Qsort(int st, int dr);


int main ()
{
	freopen ("infasuratoare.in","r",stdin);
	freopen ("infasuratoare.out","w",stdout);
	scanf ("%d",&n);
	max=0;
	for (i=0;i<n;i++)
	{
		scanf ("%lf%lf",&p[i][0],&p[i][1]);
		if (p[i][1]>p[max][1]||(abs(p[i][1]-p[max][1])<0.001&&p[i][0]>p[max][0]))
			max=i;
	}
	aux[0]=p[0][0];
	aux[1]=p[0][1];
	p[0][0]=p[max][0];
	p[0][1]=p[max][1];
	p[max][0]=aux[0];
	p[max][1]=aux[1];
	Qsort(1,n-1);
	pct=2;
	pol[0]=0; pol[1]=1;
	for (i=2;i<n;i++)
	{
		while (cross(p[pol[pct-2]],p[pol[pct-1]],p[i])<0)
			pct--;
		pol[pct]=i;
		pct++;
	}
	printf("%d\n",pct);
	for (i=0;i<pct;i++)
		printf("%lf %lf\n",p[pol[i]][0],p[pol[i]][1]);
	return 0;
}

int aranjare (int st, int dr)
{
	double aux[2];
	aux[0]=p[st][0];
	aux[1]=p[st][1];
	while (st<dr)
	{
		while ((st<dr)&&(cross(p[0],aux,p[dr])>=0)) dr--;
		if (st<dr)
			{p[st][0]=p[dr][0];
			p[st][1]=p[dr][1];}
		while ((st<dr)&&(cross(p[0],aux,p[st])<=0)) st++;
		if (st<dr)
			{p[dr][0]=p[st][0];p[dr][1]=p[st][1];}
	}
	p[st][0]=aux[0];
	p[st][1]=aux[1];
	return st;
}

void Qsort (int st, int dr)
{
	int poz;
	if (st<dr)
	{
		poz=aranjare(st,dr);
		Qsort(st,poz-1);
		Qsort(poz+1,dr);
	}
}