Cod sursa(job #493123)

Utilizator indestructiblecont de teste indestructible Data 17 octombrie 2010 11:21:51
Problema Gradina Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.95 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NMAX 255
#define ll long long
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],ord[NMAX];
ll a,b,c,val,arie1,arie2,rez=-1;
char marc[NMAX],sol[NMAX],uz[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 d,int e)
{
	int i;
	memset(marc,0,sizeof(marc));
	r=t=0;
	for (i=1; i<=n; i++)
	{
		val=a*D[i].x+b*D[i].y+c;
		if (i!=d && i!=e)
		{
			if (val<0)
				B[++r]=i;
			if (val>0)
				C[++t]=i,marc[ord[i]]=1;
		}
		if (i==d)
			B[++r]=i;
		if (i==e)
			C[++t]=i,marc[ord[i]]=1;
	}
}
void init1()
{
	p=0;
	int i;
	for (i=1; i<=r; i++)
		H[i].x=D[B[i]].x,H[i].y=D[B[i]].y;
	for (i=1; i<=r; i++)
		E[++p]=i;
}
void init2()
{
	p=0;
	int i;
	for (i=1; i<=t; i++)
		H[i].x=D[C[i]].x,H[i].y=D[C[i]].y;
	for (i=1; i<=t; i++)
		E[++p]=i;
}
inline int semn(int a,int b,int c)
{
	ll A=H[a].y-H[b].y;
	ll B=H[b].x-H[a].x;
	ll C=(ll)H[a].x*H[b].y-(ll)H[b].x*H[a].y;
	ll value=A*H[c].x+B*H[c].y+C;
	return (value<0);
}
int infasuratoare(int s)
{
	int i;
	h=0;
	st[++h]=1; st[++h]=2;
	for (i=3; i<=p; i++)
	{
		while (h>=2 && semn(st[h-1],st[h],E[i]))
			h--;
		st[++h]=E[i];
	}
	for (i=p-1; i>=1; i--)
	{
		while (h>=2 && semn(st[h-1],st[h],E[i]))
			h--;
		st[++h]=E[i];
	}
	h--;
	if (h!=s)
		return 0;
	return 1;
}
inline ll modul(ll x)
{
	return x<0 ? -x : x;
}
ll arie(int x,int y,int z)
{
	ll val=(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);
	return modul(val);
}
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));
}
void solve2()
{
	int k;
	init1();
	if (infasuratoare(r))
	{
		arie1=0;
		for (k=2; k<h; k++)
			arie1+=arie(st[1],st[k],st[k+1]);
		init2();
		if (infasuratoare(t))
		{
			arie2=0;
			for (k=2; k<h; k++)
				arie2+=arie(st[1],st[k],st[k+1]);
			val=modul(arie1-arie2);
			if (rez>-1)
			{
				//if (rez==val)
				//	act_sol();
				if (rez>val)
				{
					rez=val;
					memcpy(sol,marc,sizeof(marc));
				}
			}
			else
			{
				rez=val;
				memcpy(sol,marc,sizeof(marc));
			}
		}
	}
}
bool comp2(pct a,pct b)
{
	return a.y<b.y || (a.y==b.y && a.x<b.x);
}
bool comp(int a,int b)
{
	return D[a].y<D[b].y || (D[a].y==D[b].y && D[a].x<D[b].x);
}
void solve()
{
	int i,j;
	for (i=1; i<=n; i++)
		ord[i]=i;
	sort(ord+1,ord+n+1,comp);
	sort(D+1,D+n+1,comp2);
	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;
				preg(i,j);
				solve2();
			}
}
int main()
{
	freopen("gradina.in","r",stdin);
	freopen("gradina.out","w",stdout);
	read();
	solve();
	printf("%.1lf\n",(double)rez/2);
	for (int i=1; i<=n; i++)
		if (!sol[i])
			printf("I");
		else
			printf("V");
	printf("\n");
	return 0;
}