Cod sursa(job #534702)

Utilizator ilincaSorescu Ilinca ilinca Data 16 februarie 2011 00:11:41
Problema Gradina Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.17 kb
#include <cstdio>
#include <cstring>
#include <climits>
#include <vector>
#include <algorithm>

#define nmax 255
#define x first
#define y second

using namespace std;

typedef pair <int, int> ii;

int n, a [2] [nmax], c [2] [nmax];
bool v [nmax];
char x [nmax], xmin [nmax];
ii p [nmax];
pair <ii, int> ceva [nmax];


void scan ()
{
	int i;
	scanf ("%d", &n);
	for (i=1; i <= n; ++i)
	{
		scanf ("%d%d", &p [i].x, &p [i].y);
		ceva [i]=make_pair (p [i], i);
	}
}

int semn (int i1, int i2, int i3)
{
	int a=p [i1].y-p [i2].y, b=p [i2].x-p [i1].x, c=p [i1].x*p [i2].y - p [i1].y*p [i2].x;
	return a*p [i3].x + b*p [i3].y + c;
}

void sep (int i1, int i2)
{
	int i, k, i12, i22;
	i12=i1;
	i22=i2;
	if ((p [i1].x > p [i2].x) || ((p [i1].x == p [i2].x) && (p [i1].y > p [i2].y)))
	{
		i12=i2;
		i22=i1;
	}
	a [0] [0]=a [1] [0]=0;
	for (i=1; i <= n; ++i)
	{
		if (i == i12)
		{
			a [0] [++a [0] [0]]=i;
			continue;
		}
		if (i == i22)
		{
			a [1] [++a [1] [0]]=i;
			continue;
		}
		if (semn (i1, i2, i) < 0)
			k=0;
		else
			k=1;
		a [k] [++a [k] [0]]=i;
	}
}

inline int max (int a, int b)
{
	if (a > b) return a;
	return b;
}

void convex_hull (int a [], int pc [])
{
	int i=1, s=1, k=0;
	memset (v, 0, sizeof (v));
	pc [++k]=1;
	while (v [1] == false)
	{
		do
		{
			i += s;
			if (i == a [0]) s = -1;
		} while (v [i] == true);
		while (k >= 2 && semn (a [pc [k-1]], a [pc [k]], a [i]) <0)
			v [pc [k--]]=false;
		pc [++k]=i;
		v [i]=true;
	}
	pc [0]=k;
	for (i=1; i <= pc [0]; ++i)
		pc [i]=a [pc [i]];
}

int arie (int pc [])
{
	int i, A=0;
//	pc [++pc [0]]=pc [1];
	for (i=2; i+1 < pc [0]; ++i)
		A += (p [pc [i]].x-p [pc [1]].x) * (p [pc [i+1]].y-p [pc [1]].y) - (p [pc [i]].y-p [pc [1]].y) * (p [pc [i+1]].x-p [pc [1]].x);
	return A;
}

int rez ()
{
	int A1, A2;
	if (a [0] [0] < 3 || a [1] [0] < 3) return INT_MAX;
	convex_hull (a [0], c [0]);
	convex_hull (a [1], c [1]);
//	for (int i=1; i <= a [0] [0]; ++i) fprintf (stderr, "%d\n", a [0] [i]);
//	fprintf (stderr, "\n");
	A1=arie (c [0]);
	A2=arie (c [1]);
	A1=max (A1, -A1);
	A2=max (A2, -A2);
	return max (A1-A2, A2-A1);
}

void init ()
{
	int i;
	for (i=1; i <= n; ++i)
		p [i]=ceva [i].first;
}

int cmp (char a [], char b [])
{
	//1 => a > b
	//0 => a = b
	//-1 => a < b
	int i;
	for (i=1; i <= n; ++i)
	{
		if (a [i] == b [i]) continue;
		if (a [i] > b [i]) return 1;
		return -1;
	}
	return 0;
}

void form_sir ()
{
	char c1='I', c2='V';
	int i, ind=0;
	if (a [1] [1] == 1)
	{
		c1='V';
		c2='I';
	}
	for (i=1; i <= n; ++i)
		if (ind+1 <= a [0] [0] && a [0] [ind+1] == i)
		{
			x [ceva [i].second]=c1;
			++ind;
		}
		else
			x [ceva [i].second]=c2;
	x [n+1]=0;
}

int main ()
{
	freopen ("gradina.in", "r", stdin);
	freopen ("gradina.out", "w", stdout);
	scan ();
	sort (ceva+1, ceva+1+n);
	init ();
	int i, j, r, min=INT_MAX;
	for (i=1; i <= n; ++i)
		for (j=1; j <= n; ++j)
			if (i != j)
			{
				sep (i, j);
				r=rez ();
				if (min < r) continue;
				form_sir ();
				//fprintf (stderr, "%d %d %s %s\n", i, j, x+1, xmin+1);
				if (min == r && cmp (xmin, x) > 0)
					memcpy (xmin, x, sizeof (x));	
				if (min > r)
				{
					min=r;
					memcpy (xmin, x, sizeof (x));	
				}
			}	
	printf ("%.1lf\n", (double)min/2.0);
	printf ("%s\n", xmin+1);
	return 0;
}