Cod sursa(job #384568)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 20 ianuarie 2010 13:44:43
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMAX 120001
#define pb push_back
using namespace std;
struct pct
{
	double a,b;
};
pct v[NMAX];
int n,sol[NMAX],r,ord[NMAX];
vector <int> A[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=i+1; j<=n; 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;
				A[i].pb(j);
				A[j].pb(i);
			}
		}
}
void reconst(int poz)
{
	printf("%lf %lf\n",v[poz].a,v[poz].b);
	marc[poz]=1;
	int i,best=0;
	for (i=0; i<A[poz].size(); i++)
	{
		if (!marc[A[poz][i]])
		{
			//if (!
		}
	}
}
void show()
{
	int i,bestp;
	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;
		}
	}
	for (i=1; i<=r; i++)
		printf("%lf %lf\n",v[sol[i]].a,v[sol[i]].b);
	//reconst(sol[bestp]);
}
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	read();
	solve();
	show();
	return 0;
}