Pagini recente » Cod sursa (job #328551) | Cod sursa (job #663452) | Cod sursa (job #350655) | Cod sursa (job #305010) | Cod sursa (job #993422)
Cod sursa(job #993422)
#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, o, s;
bitset <NMAX> in_stack;
char S[NMAX], R[NMAX];
inline long long modul (long long a) {
if (a < 0)
return -a;
return a;
}
inline long long cross_product (const point &a, const point &b, const point &c) {
return (b.x - a.x) * 1LL * (c.y - a.y) - (b.y - a.y) * 1LL * (c.x - a.x);
}
void convex_hull (const int &N, int *P) {
head = 2;
in_stack.set ();
_stack[1] = P[1];
_stack[2] = P[2];
in_stack[P[1]] = in_stack [P[2]] = 0;
for (o = 3; o <= N; ++o) {
while (cross_product (V[P[o]], V[_stack[head - 1]], V[_stack[head]]) < 0 && head > 1)
in_stack[_stack[head--]] = 1;
in_stack[_stack[++head] = P[o]] = 0;
}
for (o = N - 1; o > 1; --o) {
if (!in_stack[P[o]])
continue;
while (cross_product (V[P[o]], V[_stack[head - 1]], V[_stack[head]]) < 0 && head > 1)
--head;
_stack[++head] = P[o];
}
}
inline long long aria () {
long long A = 0;
_stack[++head] = _stack[1];
for (o = 1; o < head; ++o)
A += cross_product (V[0], V[_stack[o]], V[_stack[o + 1]]);
return modul (A);
}
inline void make_solution () {
for (o = 1; o <= l; ++o)
S[V[ind[o]].p] = 'I';
for (o = 1; o <= _l; ++o)
S[V[_ind[o]].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;
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]) > 0 ? ind[++l] = k : _ind[++_l] = k;
if (l < 3 || _l < 3)
continue;
convex_hull (l, ind);
if (head != l)
continue;
A = aria ();
convex_hull (_l, _ind);
if (head != _l)
continue;
_A = aria ();
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\n%s", (double) DIFF / 2.0, R);
}