Cod sursa(job #728811)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 28 martie 2012 23:34:33
Problema Gradina Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define nmax 255

struct punct
{
	int x, y, p;
} v[nmax];

vector <int> a, b;
char sv[nmax], solv[nmax];
int n, h, st[nmax], u[nmax];
double sol;

int cmp (punct a, punct b)
{
	if (a.x == b.x) return a.y < b.y;
	return a.x < b.x;
}

long long semn (int i, int j, int k)
{
	long long a, b, c;
	a = v[i].y - v[j].y;
	b = v[j].x - v[i].x;
	c = (long long) v[i].x * v[j].y - (long long) v[j].x * v[i].y;
	return a * v[k].x + b * v[k].y + c;
}

double convex_hull (vector <int> a)
{
	int i, stp;
	for (i=0; i < a.size(); i++) u[i] = 0;
	u[0] = 1;
	h = 1;
	st[1] = 0;
	stp = 1;
	for (i=1; ; i+=stp)
	{
		if (!u[i])
		{
			while (semn (a[st[h-1]], a[st[h]], a[i]) < 0 && h > 1) u[st[h--]] = 0;
			st[++h] = i;
			u[i] = 1;
		}
		if (i == a.size()-1) stp = -1;
		if (stp == -1 && !i) break;
	}
	if (h != a.size()) return -1;
	st[h+1] = st[1];
	double area = 0;
	for (i=1; i <= h; i++) area += (long long) v[a[st[i]]].x * v[a[st[i+1]]].y - (long long) v[a[st[i+1]]].x * v[a[st[i]]].y;
	if (area < 0) area = -area;
	area *= 0.5;
	return area;
}
	

int main()
{
	freopen ("gradina.in", "r", stdin);
	freopen ("gradina.out", "w", stdout);
	scanf ("%d", &n);
	int i, j, k, ok;
	char c1, c2;
	double ar1, ar2, d;
	sol = 1<<30;
	for (i=1; i <= n; i++) 
	{
		scanf ("%d %d", &v[i].x, &v[i].y);
		v[i].p = i;
	}
	sort (v+1, v+n+1, cmp);
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			if (i != j)
			{
				a.erase (a.begin(), a.end());
				b.erase (b.begin(), b.end());
				for (k=1; k<=n; k++)
					if (k == i) a.push_back (k); else
						if (k == j) b.push_back (k); else
							if (semn (i, j, k) < 0) a.push_back (k); else
								b.push_back (k);
				if (a.size () < 3 || b.size() < 3) continue;
				ar1 = convex_hull (a);
				ar2 = convex_hull (b);
				if (ar1 == -1 || ar2 == -1) continue;
				d = ar1 - ar2;
				if (d < 0) d = -d;
				if (d <= sol)
				{
					if (a[0] == 1) 
					{
						c1 = 'I'; 
						c2 = 'V';
					} else 
					{
						c1 = 'V';
						c2 = 'I';
					}
					for (k = 0; k < a.size(); k++) sv[v[a[k]].p] = c1;
					for (k = 0; k < b.size(); k++) sv[v[b[k]].p] = c2;
					ok = 0;
					if (d != sol) ok = 1; else
						for (k = 1; k <= n; k++) 
							if (sv[k] < solv[k])
							{
								ok = 1;
								break;
							}
					if (ok)
						for (k = 1; k <= n; k++) solv[k] = sv[k];
					sol = d;
				}
			}
	printf ("%.1lf\n", sol);
	for (i=1; i<=n; i++) printf ("%c",solv[i]);
}