Cod sursa(job #325604)

Utilizator wefgefAndrei Grigorean wefgef Data 21 iunie 2009 15:28:29
Problema Gradina Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>

using namespace std;

#define sz(c) int((c).size())
#define pb push_back
#define all(c) (c).begin(), (c).end()

#define inf 1000000000 //un miliard
#define Nmax 256

struct punct {
	int x, y, z;
	bool operator < (const punct& p) const {
		return x != p.x ? x < p.x : y < p.y;
	}
};

int n;
punct pt[Nmax];

vector<int> v, u;
vector<char> aux;

int best = inf;
vector<char> ret;

char viz[Nmax];
int st[Nmax], cnt;

void readdata()
{
	freopen("gradina.in", "r", stdin);
	freopen("gradina.out", "w", stdout);

	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d %d", &pt[i].x, &pt[i].y);
		pt[i].z = i;
	}
}

int arie(vector<int> &v)
{
	int i, ret = 0;

	for (i = 0; i < sz(v)-1; ++i)
		ret += pt[v[i]].x * pt[v[i+1]].y - pt[v[i]].y * pt[v[i+1]].x;
	return abs(ret);
}

int sign(int a, int b, int c)
{
	return (pt[a].x-pt[c].x)*(pt[b].y-pt[c].y) - (pt[b].x-pt[c].x)*(pt[a].y-pt[c].y) < 0;
}

int convex_hull(vector<int> &v)
{
	int i, p = 1, nr = sz(v);
	vector<int> aux;

	if (nr < 3) return 0;

	memset(viz, 0, sizeof(viz));
	st[cnt = 0] = 0;
	for (i = 1; i >= 0; i += (p = (i == sz(v)-1 ? -p : p)))
		if (!viz[i])
		{
			while (cnt >= 1 && sign( v[i], v[st[cnt]], v[st[cnt-1]] ))
				viz[ st[cnt--] ] = 0;
			viz[ st[ ++cnt ] = i ] = 1;
		}

	for (i = 0; i <= cnt; ++i)
		aux.pb( v[ st[i] ]);
	v = aux;
	return cnt == nr;
}

void eval(vector<int> &v, vector<int> &u)
{
	int tmp, i;

	if (convex_hull(u) && convex_hull(v))
	{
		tmp = abs(arie(v) - arie(u));
		if (tmp > best) return;

		for (i = 0; i < sz(v)-1; ++i)
			aux[ pt[v[i]].z ] = 'I';
		for (i = 0; i < sz(u)-1; ++i)
			aux[ pt[u[i]].z ] = 'V';
		if (aux[0] == 'V')
			for (i = 0; i < n; ++i)
				if (aux[i] == 'I') aux[i] = 'V';
				else aux[i] = 'I';

		if (tmp < best)
		{
			best = tmp;
			ret = aux;
		}
		if (aux < ret) ret = aux;
	}
}

void solve()
{
	int i, j, k;

	sort(pt, pt+n);

	aux.resize(n);
	for (i = 0; i < n; ++i)
		for (j = 0; j < n; ++j)
			if (i != j)
			{
				v.clear(); u.clear();
				for (k = 0; k < n; ++k)
					if (k != i && k != j)
						if (sign(k, j, i)) v.pb(k);
						else u.pb(k);
					else
						if (k == i) v.pb(k);
						else u.pb(k);
				eval(v, u);
			}
}

void writedata()
{
	printf("%.1lf\n", (double)best/(double)2);
	for (int i = 0; i < sz(ret); ++i)
		printf("%c", ret[i]);
}

int main()
{
	readdata();
	solve();
	writedata();
	return 0;
}