Cod sursa(job #652975)

Utilizator suzanicaSuzanica Mihu suzanica Data 26 decembrie 2011 22:51:11
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
# include <cstdio> 

using namespace std;

int maix,n,i,pct;
double aux[2];
int pol[120005];
double p[120005][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);
	maix=0;
	for (i=0;i<n;i++)
	{
		scanf("%lf%lf",&p[i][0],&p[i][1]);
		if (p[i][0]<p[maix][0])
			maix=i;
		else if (p[i][0]==p[maix][0]&&p[i][1]<p[i][1])
			maix=i;
	}
	aux[0]=p[0][0];
	aux[1]=p[0][1];
	p[0][0]=p[maix][0];
	p[0][1]=p[maix][1];
	p[maix][0]=aux[0];
	p[maix][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);
	}
}