Cod sursa(job #720947)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 23 martie 2012 08:19:48
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.03 kb
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#define NMAX 260
#define EPS 1e-10

using namespace std;

struct punct 
{
	int x, y, o;
} a[NMAX], an[NMAX], ap[NMAX], aux;
int n, nn, np;
char AUX[NMAX], SOL[NMAX];
double mn=10000000000.0;

inline bool cmp(punct A, punct B)
{
	if (A.x<B.x || (A.x==B.x && A.y<B.y)) return 1;
	return 0;
}

inline int plan(punct A, punct B, punct C)
{
	return A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-C.y*A.x-A.y*B.x;
}

void Intercalare(punct v[], punct A, int &n)
{
	int i;
	bool ok = true;
	for (i=n; i>0; --i)
		if (v[i].x>A.x || (v[i].x==A.x && v[i].y>A.y)) v[i+1]=v[i];
		else 
		{
			v[i+1]=A;
			ok = false;
			break;
		}
	if (ok) v[1] = A;
	++n;
}

void Sterge(punct v[], punct A, int &n)
{
	int i, gas=0;
	for (i=1; i<n; ++i)
		if (!gas)
		{
			if (v[i].o==A.o) 
			{
				gas=1;
				v[i]=v[i+1];
			}
		}
		else v[i]=v[i+1];
	--n;
}
inline int prod(punct A, punct B) {
	return (A.x-B.x)*(A.y+B.y);
}

double Arie(punct v[], int n)
{
	int S=0, i;
	for (i=1; i<n; ++i)
		S+=prod(v[i], v[i+1]);
	S += prod(v[n], v[1]);
	S = abs(S);
	return (double)S/2;
}

int Infasoara(punct v[], int n)
{
	int vz[NMAX], ord[NMAX], S[NMAX], i, j, m=2;
	
	for (i=1, j=n+n; i<=n; ++i, --j) 
	{
		vz[i]=0;
		ord[i]=ord[j]=i;
	}
	
	S[1]=1; S[2]=2; vz[2]=1;
	for (i=3; i<=n+n; ++i)
		if (!vz[ord[i]])
		{
			while (m>1 && plan(v[S[m]], v[S[m-1]], v[ord[i]])<0)
			{
				vz[S[m]]=0; S[m--]=0;
			}
			S[++m]=ord[i]; vz[ord[i]]=1;
		}
	
	m=0;
	for (i=1; i<=n; ++i) m+=vz[i];
	
	if (m==n) return 1;
	return 0;
}

void Construieste(char drum[])
{
	int i, gas=0;
	for (i=1; i<=nn; ++i)
		if (an[i].o==1)
		{
			gas=1;
			break;
		}
	if (gas)
	{
		for (i=1; i<=nn; ++i) drum[an[i].o-1]='I';
		for (i=1; i<=np; ++i) drum[ap[i].o-1]='V';
	}
	else
	{
		for (i=1; i<=nn; ++i) drum[an[i].o-1]='V';
		for (i=1; i<=np; ++i) drum[ap[i].o-1]='I';
	}
}

void Imparte(int i, int j)
{
	double A;
	Intercalare(an, a[i], nn);
	Intercalare(ap, a[j], np);
	if (Infasoara(an, nn) && Infasoara(ap, np))
	{
		A=fabs(Arie(an, nn)-Arie(ap, np));
		if (mn-A>EPS) 
		{
			mn=A;
			Construieste(SOL);
		}
		else 
			if (fabs(mn-A)<EPS)
			{
				Construieste(AUX);
				if (strcmp(AUX, SOL)<0) strcpy(SOL, AUX);
			}
	}
	Sterge(an, a[i], nn);
	Sterge(ap, a[j], np);
}

void Solve(int i, int j)
{
	int k, P;
	
	nn=0, np=0;
	for (k=1; k<=n; ++k)
		if (k!=i && k!=j)
		{
			P=plan(a[i], a[j], a[k]);
			if (P<0) an[++nn]=a[k];
			else ap[++np]=a[k];
		}
	if (nn>1 && np>1)
	{
		Imparte(i, j);
		Imparte(j, i);
	}
	for (k=1; k<=n; ++k) an[k]=ap[k]=aux;
}

int main()
{
	int i, j;
	freopen("gradina.in", "r", stdin);
	freopen("gradina.out", "w", stdout);
	
	scanf("%d", &n);
	for (i=1; i<=n; ++i) 
	{
		scanf("%d %d", &a[i].x, &a[i].y);
		a[i].o=i;
	}
	
	sort(a+1, a+n+1, cmp);
	
	for (i=1; i<n; ++i)
		for (j=i+1; j<=n; ++j) 
			Solve(i, j);
	
	printf("%.3f\n", mn);
	printf("%s", SOL);
	return 0;
}