Cod sursa(job #384569)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 20 ianuarie 2010 14:13:26
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.27 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMAX 120001
using namespace std;
struct pct
{
	double a,b;
};
pct v[NMAX];
int n,sol[NMAX],r,ord[NMAX];
int A[NMAX],B[NMAX];
double a,b,c;
char viz[NMAX],marc[NMAX];
void read()
{
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
		scanf("%lf%lf",&v[i].a,&v[i].b);
}
inline int sign(int k)
{
	double rez=v[k].a*a-v[k].b*b+c;
	if (rez<=0)
		return 0;
	return 1;
}
void solve()
{
	int i,j,k;
	char tip,tb,ok;
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++)
			if (i!=j)
			{
				tb=5; ok=1;
				a=v[i].b-v[j].b;
				b=v[i].a-v[j].a;
				c=v[i].a*v[j].b-v[j].a*v[i].b;
				for (k=1; k<=n; k++)
					if (k!=i && k!=j)
					{
						tip=sign(k);
						if (tb==5)
							tb=tip;
						else
							if (tb!=tip)
							{
								ok=0;
								break;
							}
					}
				if (ok)
				{
					if (!viz[i])
					{
						sol[++r]=i,viz[i]=1;
					}
					if (!viz[j])
						sol[++r]=j,viz[j]=1;
					if (!A[i])
						A[i]=j;
					else
						B[i]=j;
					if (!A[j])
						A[j]=i;
					else
						B[j]=i;
				}
			}
}
void show()
{
	int i,bestp,j,pozitie;
	printf("%d\n",r);
	double x,y;
	x=v[sol[1]].a; y=v[sol[1]].b; bestp=1;
	for (i=2; i<=r; i++)
	{
		if (v[sol[i]].b==y && v[sol[i]].a<x)
		{
			x=v[sol[i]].a;
			bestp=i;
		}
		if (v[sol[i]].b<y)
		{
			y=v[sol[i]].b;
			x=v[sol[i]].a;
			bestp=i;
		}
	}
	printf("%lf %lf\n",v[sol[bestp]].a,v[sol[bestp]].b);
	j=sol[bestp];
	marc[j]=1;
	a=v[j].b-v[A[j]].b;
	b=v[j].a-v[A[j]].a;
	c=v[j].a*v[A[j]].b-v[A[j]].a*v[j].b;
	int ans1=sign(B[j]);
	a=v[j].b-v[B[j]].b;
	b=v[j].a-v[B[j]].a;
	c=v[j].a*v[B[j]].b-v[B[j]].a*v[j].b;
	int ans2=sign(A[j]);
	if (ans1)
		pozitie=A[j];
	else
		pozitie=B[j];
	while (1)
	{
		printf("%lf %lf\n",v[pozitie].a,v[pozitie].b);
		marc[pozitie]=1;
		if (!marc[A[pozitie]])
			pozitie=A[pozitie];
		if (!marc[B[pozitie]])
			pozitie=B[pozitie];
		if (marc[A[pozitie]] && marc[B[pozitie]])
		{
			if (!marc[A[j]])
				printf("%lf %lf\n",v[A[j]].a,v[A[j]].b);
			else
				printf("%lf %lf\n",v[B[j]].a,v[B[j]].b);
			return ;
		}
	}
}
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	read();
	solve();
	show();
	return 0;
}