Cod sursa(job #493063)

Utilizator indestructiblecont de teste indestructible Data 16 octombrie 2010 21:32:24
Problema Gradina Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.39 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NMAX 255
#define ll long long
#define prec 0.000001
using namespace std;
struct pct
{
	int x,y;
};
pct D[NMAX],H[NMAX];
int n,B[NMAX],C[NMAX],r,t,p,h,PI,E[NMAX],st[NMAX];
ll a,b,c,val;
double arie1,arie2,rez=-1;
char marc[NMAX],sol[NMAX];
void read()
{
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
		scanf("%d%d",&D[i].x,&D[i].y);
}
void preg(int g)
{
	int i;
	for (i=1; i<=n; i++)
	{
		val=a*D[i].x+b*D[i].y+c;
		if (val*g<0)
			B[++r]=i;
		if (val*g>0)
			C[++t]=i,marc[i]=1;
	}
}
void init1()
{
	p=0;
	int i;
	PI=1;
	for (i=1; i<=r; i++)
	{
		H[i].x=D[B[i]].x,H[i].y=D[B[i]].y;
		if (H[i].x<H[PI].x || (H[i].x==H[PI].x && H[i].y<H[PI].y))
			PI=i;
	}
	for (i=1; i<=r; i++)
		if (i!=PI)
			E[++p]=i;
}
void init2()
{
	p=0;
	int i;
	PI=1;
	for (i=1; i<=t; i++)
	{
		H[i].x=D[C[i]].x,H[i].y=D[C[i]].y;
		if (H[i].x<H[PI].x || (H[i].x==H[PI].x && H[i].y<H[PI].y))
			PI=i;
	}
	for (i=1; i<=t; i++)
		if (i!=PI)
			E[++p]=i;
}
bool comp(int i,int j)
{
	return (ll)(H[i].x - H[PI].x) * (H[j].y - H[PI].y) < (ll)(H[j].x - H[PI].x) * (H[i].y - H[PI].y);
}
ll semn(int i1,int i2,int i3)
{
	return (ll)H[i1].x * H[i2].y +(ll) H[i2].x * H[i3].y + (ll) H[i3].x * H[i1].y -(ll) H[i1].y * H[i2].x -(ll) H[i2].y * H[i3].x -(ll) H[i3].y * H[i1].x;
}
int infasuratoare(int s)
{
	int i;
	for (i=1; i<=p; i++)
	{
		while (h>=2 && semn(st[h-1],st[h],E[i])>0)
			h--;
		st[++h]=E[i];
	}
	if (h!=s)
		return 0;
	return 1;
}
inline ll modul2(ll x)
{
	return x<0 ? -x : x;
}
ll arie(int x,int y,int z)
{
	return modul2((ll)(H[y].x-H[x].x)*(H[z].y-H[x].y)-(ll)(H[y].y-H[x].y)*(H[z].x-H[x].x));
}
inline double modul(double x)
{
	return x<0 ? -x : x;
}
inline double min(double x,double y)
{
	return x<y ? x : y;
}
void act_sol()
{
	int i,tip=0;
	for (i=1; i<=n; i++)
	{
		if (sol[i]<marc[i])
			break ;
		if (sol[i]>marc[i])
		{
			tip=1;
			break ;
		}
	}
	if (tip)
		memcpy(sol,marc,sizeof(marc));
}
inline double egal(double x,double y)
{
	return -prec<x-y && x-y<prec;
}
void solve2()
{
	int k;
	init1();
	sort(E+1,E+p+1,comp);
	h=0;
	st[++h]=PI;
	if (infasuratoare(r))
	{
		st[++h]=PI;
		arie1=0;
		for (k=2; k<=h; k++)
			arie1+=arie(PI,st[k],st[k+1])/2;
		init2();
		sort(E+1,E+p+1,comp);
		h=0;
		st[++h]=PI;
		if (infasuratoare(t))
		{
			st[++h]=PI;
			arie2=0;
			for (k=2; k<=h; k++)
				arie2+=arie(PI,st[k],st[k+1])/2;
			if (rez>-1)
			{
				if (rez>modul(arie1-arie2))
				{
					rez=modul(arie1-arie2);
					memcpy(sol,marc,sizeof(marc));
				}
				if (egal(rez,modul(arie1-arie2)))
					act_sol();
			}
			else
			{
				rez=modul(arie1-arie2);
				memcpy(sol,marc,sizeof(marc));
			}
		}
	}
}
void solve()
{
	int i,j;
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++)
			if (i!=j)
			{
				a=-D[j].y+D[i].y;
				b=-D[i].x+D[j].x;
				c=(ll)D[i].x*D[j].y-(ll)D[j].x*D[i].y;
				r=t=0; 
				memset(marc,0,sizeof(marc));
				B[++r]=i; C[++t]=j;
				marc[j]=1;
				preg(1);
				solve2();
				memset(marc,0,sizeof(marc));
				r=t=1;
				marc[j]=1;
				preg(-1);
				solve2();
			}
}
int main()
{
	freopen("gradina.in","r",stdin);
	freopen("gradina.out","w",stdout);
	read();
	solve();
	printf("%.1lf\n",rez);
	for (int i=1; i<=n; i++)
		if (!sol[i])
			printf("I");
		else
			printf("V");
	printf("\n");
	return 0;
}