Cod sursa(job #625740)

Utilizator matemariaescuMaria Mateescu matemariaescu Data 25 octombrie 2011 13:39:10
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
# include <fstream.h> 
# include <math.h>
# define ABS(x) x>0?x:(-x)

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

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

long double dot(long double A[], long double B[], long double C[])
{
    long double AB[2];
    long 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];
    long double d = AB[0] * BC[0] + AB[1] * BC[1];
    return d;
}

long double cross(long double A[], long double B[], long double C[])
{
    long double AB[2];
    long 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];
    long 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 ()
{
	fin>>n;
	max=0;
	for (i=0;i<n;i++)
	{
		fin>>p[i][0]>>p[i][1];
		if (p[i][1]<p[max][1]||(ABS(p[i][1]-p[max][1])<0.000000000001&&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++;
	}
	fout<<pct<<'\n';
	for (i=0;i<pct;i++)
		fout<<p[pol[i]][0]<<' '<<p[pol[i]][1]<<'\n';
	return 0;
}

int aranjare (int st, int dr)
{
	long 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);
	}
}