Pagini recente » Cod sursa (job #2045080) | Solutii preONI 2007, Runda 4 | Cod sursa (job #1002846) | Cod sursa (job #1232247) | Cod sursa (job #1003459)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <bitset>
#define x first.first
#define y first.second
#define p second
using namespace std;
typedef pair <pair <int, int>, int> point;
const int NMAX = 253;
point V[NMAX];
int ind[NMAX], _ind[NMAX], _stack[NMAX], l, _l, head, s, p;
bitset <NMAX> in_stack;
char S[NMAX];
inline long long modul (long long a) {
if (a < 0)
return -a;
return a;
}
inline bool cross_product (const point &a, const point &b, const point &c) {
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0 ;
}
void convex_hull (const int &N, int *P) {
int i;
head = 2;
p = 1;
in_stack.set ();
_stack[1] = P[1];
_stack[2] = P[2];
in_stack[P[1]] = in_stack [P[2]] = 0;
for (i = 3; i > 1; i += p) {
if (!in_stack[P[i]])
continue;
while (!cross_product (V[P[i]], V[_stack[head - 1]], V[_stack[head]]) && head >= 2)
in_stack[_stack[head--]] = 1;
in_stack[_stack[++head] = P[i]] = 0;
if (i == N)
p = -1,
in_stack[P[1]] = 1;
}
}
inline void make_solution () {
int i;
for (i = 1; i <= l; ++i)
S[V[ind[i]].p] = 'I';
for (i = 1; i <= _l; ++i)
S[V[_ind[i]].p] = 'V';
}
int main () {
freopen ("gradina.in", "r", stdin);
freopen ("gradina.out", "w", stdout);
long long A, _A, DIFF = 2e18;
int N, i, j, k, m;
char R[NMAX];
scanf ("%d", &N);
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);
for (i = 1; i <= N; ++i)
for (j = 1; j <= N; ++j)
if (i != j) {
l = _l = 0;
for (k = 1; k <= N; ++k)
if (k == i)
ind[++l] = k;
else
if (k == j)
_ind[++_l] = k;
else
cross_product (V[i], V[j], V[k]) ? ind[++l] = k : _ind[++_l] = k;
if (l < 3 || _l < 3)
continue;
convex_hull (l, ind);
if (head != l)
continue;
A = 0;
_stack[++head] = _stack[1];
for (m = 1; m < head; ++m)
A += 1LL * V[_stack[m]].x * V[_stack[m + 1]].y - 1LL * V[_stack[m]].y * V[_stack[m + 1]].x;
A = modul (A);
convex_hull (_l, _ind);
if (head != _l)
continue;
_A = 0;
_stack[++head] = _stack[1];
for (m = 1; m < head; ++m)
_A += 1LL * V[_stack[m]].x * V[_stack[m + 1]].y - 1LL * V[_stack[m]].y * V[_stack[m + 1]].x;
_A = modul (_A);
if (modul (A - _A) < DIFF) {
DIFF = modul (A - _A);
make_solution ();
strcpy (R, S + 1);
}
else
if (modul (A - _A) == DIFF) {
make_solution ();
if (strcmp (S + 1, R) < 0)
strcpy (R, S + 1);
}
}
printf ("%.1lf", (double) DIFF / 2.0);
printf ("\n%s", R);
}