Cod sursa(job #534899)

Utilizator ilincaSorescu Ilinca ilinca Data 16 februarie 2011 15:04:00
Problema Gradina Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.05 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, m [2] [nmax], ch [2] [nmax];
char smin [nmax], s [nmax];
bool viz [nmax];
ii p [nmax];
pair <ii, int> o [nmax];

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

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

int semn (int i1, int i2, int i3)
{
	int a=p [i1].y-p [i2].y, b=p [i2].x-p [i1].x, c=((long long)p [i1].x)*p [i2].y - ((long long)p [i1].y)*p [i2].x;
	long long exp= ((long long)a)*p [i3].x + ((long long)b)*p [i3].y + c;
	if (exp < 0) return -1;
	if (exp > 0) return 1;
	return 0;
}

void separa (int i1, int i2, int t)
{
	int i;
	m [0] [0]=m [1] [0]=0;
	for (i=1; i <= n; ++i)
	{
		if (i == i1 || i == i2)
		{
			m [t] [++m [t] [0]]=i;
			continue;
		}
		if (semn (i1, i2, i) < 0)
			m [0] [++m [0] [0]]=i;
		else
			m [1] [++m [1] [0]]=i;
	}
}

inline long long max (long long a, long long b)
{
	return (a>b)? a:b;
}

void convex_hull (int m [], int ch [])
{
	int i=1, pas=1;
	memset (viz, 0, sizeof (viz));
	ch [0]=ch [1]=1;
	while (!viz [1])
	{
		do
		{
			i += pas;
			if (i == m [0]) pas=-1;
		} while (viz [i]);
		while (ch [0] >= 2 && semn (m [ch [ch [0]-1]], m [ch [ch [0]]], m [i]) < 0)
			viz [ch [ch [0]--]]=false;
		viz [i]=true;
		ch [++ch [0]]=i;
	}
	for (i=1; i <= ch [0]; ++i)
		ch [i]=m [ch [i]];
}

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

long long rez ()
{
	if (m [0] [0] < 3 || m [1] [0] < 3) return LLONG_MAX;
	long long A1, A2;
	convex_hull (m [0], ch [0]);
	convex_hull (m [1], ch [1]);
	A1=arie (ch [0]);
	A2=arie (ch [1]);
	A1=max (A1, -A1);
	A2=max (A2, -A2);
	return max (A1-A2, A2-A1);
}

void form_str ()
{
	int i, ind=0;
	char chr1='I', chr2='V';
	if (m [1] [0] == 1)
	{
		chr1='V';
		chr2='I';
	}
	for (i=1; i <= n; ++i)
	{
		if (ind < m [0] [0] && m [0] [ind+1] == i)
		{
			++ind;
			s [o [i].second]=chr1;
		}
		else
			s [o [i].second]=chr2;
	}
	s [n+1]=0;
}

inline int cmp (char a [], char 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;
}

int main ()
{
	freopen ("gradina.in", "r", stdin);
	freopen ("gradina.out", "w", stdout);
	scan ();
	sort (o+1, o+1+n);
	init ();
	int i, j, t;
	long long min=LLONG_MAX, r;	
	for (i=1; i <= n; ++i)
		for (j=i+1; j <= n; ++j)
			for (t=0; t <= 1; ++t)
			{
				separa (i, j, t);
				r=rez ();
				if (min > r)
				{
					min=r;
					form_str ();
					memcpy (smin, s, sizeof (s));
					continue;
				}
				if (min == r)
				{
					form_str ();
					if (cmp (smin, s) > 0) //smin mai mare lexicografic ca s
						memcpy (smin, s, sizeof (s));
				}
			}
	printf ("%.1Lf\n%s\n", (long double)min/2.0, smin+1);
	return 0;
}