Cod sursa(job #493095)

Utilizator indestructiblecont de teste indestructible Data 17 octombrie 2010 02:15:18
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.94 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];
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;
	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[i]=1;
		}
		if (i==d)
			B[++r]=i;
		if (i==e)
			C[++t]=i,marc[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;
}
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)
{
	if (s<3)
		return 0;
	memset(uz,0,sizeof(uz));
	int i,pas=1;
	h=0;
	st[++h]=1; st[++h]=2; uz[2]=1; i=2;
	while (!uz[1])
    {
        while (uz[i])
        {
           i += pas;
           if (i == s)
              pas = -1;
        }
        while (h >= 2 && semn(st[h-1], st[h], E[i]) <= 0)
			uz[st[h--]] = 0;
        st[++h] = i; uz[i] = 1;
    }
	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)
{
	return modul((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 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);
}
void solve()
{
	int i,j;
	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;
				r=t=0; 
				memset(marc,0,sizeof(marc));
				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;
}