Cod sursa(job #67584)

Utilizator gcosminGheorghe Cosmin gcosmin Data 25 iunie 2007 12:12:38
Problema Gradina Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda Finala, Clasa a 10-a Marime 2.67 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

#define NMAX 300
#define LL long long
#define ff first
#define ss second

int N;

pair <int, int> a[NMAX];

pair <pair<int, int>, int> b[NMAX];

int cc[NMAX];

string fin, aux;
string la;

int naa;
pair <int, int> aa[NMAX];
int nbb;
pair <int, int> bb[NMAX];

int st0 = 0;

inline LL semn(pair<int, int> a, pair<int, int> b, pair<int, int> c)
{
	return (LL) a.ff * (b.ss - c.ss) - (LL) a.ss * (b.ff - c.ff) + (LL) b.ff * c.ss - (LL) b.ss * c.ff;
}

int st[NMAX];
char viz[NMAX];

inline LL arie(pair <int, int> a[], int na)
{
	if (na < 3) return 0;

	st0 = 0;

	memset(viz, 0, sizeof(viz));
	
	int i, p;
	p = 1;

	st[ st0 = 1 ] = 1;

	for (i = 2; i >= 1; i += (p = (i == na) ? -p : p)) {
		if (viz[i]) continue;

		while (st0 >= 2 && semn(a[i], a[ st[ st0 - 1 ] ], a[ st[ st0 ] ]) < 0) viz[ st[ st0-- ] ] = 0;

		viz[ st[ ++st0 ] = i ] = 1;
	}

//	for (i = 1; i <= st0; i++) printf("%d %d | ", a[ st[i] ].first, a[ st[i] ].second);
//	printf("\n");

	if (st0 != na + 1) return 0;

	LL ar = 0;
	for (i = 1; i <= na; i++) 
		ar += (LL) a[ st[i] ].first * a[ st[i+1] ].second - (LL) a[ st[i] ].second * a[ st[i+1] ].first;

	if (ar < 0) return -ar;
	return ar;
}

/*
int gen(int N)
{
	freopen("gradina.in", "w", stdout);

	printf("%d\n", N);

	int i;
	for (i = 1; i <= N; i++) printf("%d %d\n", rand(), rand());

fclose(stdin);
return 0;
}
*/

int main()
{
//	gen(250);

	int i, j, k;

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

	scanf("%d", &N);

	for (i = 1; i <= N; i++) {
		scanf("%d %d", &a[i].first, &a[i].second);
		b[i].first = a[i];
		b[i].second = i;
	}

	sort(a + 1, a + N + 1);
	sort(b + 1, b + N + 1);

	for (i = 1; i <= N; i++) cc[i] = b[i].second;

	LL ar1, ar2, jg, rez = -1;

	for (i = 1; i <= N; i++) aux.push_back('0');

	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++) {
			if (i == j) continue;

			naa = nbb = 0;
			for (k = 1; k <= N; k++) {
				if (k == i) aa[++naa] = a[k], aux[k-1] = 'I';
				else 
				if (k == j) bb[++nbb] = a[k], aux[k-1] = 'V';
				else
				if (semn(a[k], a[i], a[j]) < 0) aa[++naa] = a[k], aux[k-1] = 'I';
				else bb[++nbb] = a[k], aux[k-1] = 'V';
			}

			ar1 = arie(aa, naa);
			ar2 = arie(bb, nbb);

			if (!ar1 || !ar2) continue;

			la = aux;
			for (k = 0; k < N; k++) 
				aux[ cc[k + 1] - 1 ] = la[k];

			jg = ar1 - ar2;
			if (jg < 0) jg = -jg;

			if (rez == -1) rez = jg, fin = aux;
			else 
			if (jg < rez) rez = jg, fin = aux;
			else 
			if (jg == rez && aux < fin) fin = aux;
		}

	printf("%0.1Lf\n", (long double) rez * 0.5);

	for (i = 0; i < N; i++) printf("%c", fin[i]);
	printf("\n");

fclose(stdin);
fclose(stdout);
return 0;
}