Cod sursa(job #626008)

Utilizator matemariaescuMaria Mateescu matemariaescu Data 26 octombrie 2011 07:54:30
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
# include <fstream> 
# define ABS(x) (x>0)?x:(-x)

using namespace std;

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

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

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 ()
{
	fin>>n;
	maix=0;
	for (i=0;i<n;i++)
	{
		fin>>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++;
	}
	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)
{
	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);
	}
}