Pagini recente » Cod sursa (job #777618) | Cod sursa (job #2271156) | Cod sursa (job #822857) | Cod sursa (job #3126590) | Cod sursa (job #2310412)
#include <bits/stdc++.h>
#define maxN 252
#define ll long long
#define inf 2LL * (0x3fffffff) * (0x3fffffff)
using namespace std;
FILE *fin = freopen("gradina.in", "r", stdin);
FILE *fout = freopen("gradina.out", "w", stdout);
int n;
struct Point
{
int x, y, id;
bool operator < (const Point &ot) const
{
if (x == ot.x)
return y < ot.y;
return x < ot.x;
}
} V[maxN];
int st[2][maxN];
bool vis[2][maxN];
ll ans;
char sol[2][maxN];
ll CrossProduct(Point O, Point A, Point B)
{
return 1LL * (A.x - O.x) * (B.y - O.y) - 1LL * (B.x - O.x) * (A.y - O.y);
}
ll Det(Point A, Point B)
{
return 1LL * A.x * B.y - 1LL * A.y * B.x;
}
int f(Point a, Point b, Point P)
{
if (P.x == a.x && P.y == a.y) return 0;
if (P.x == b.x && P.y == b.y) return 1;
return (1LL * (a.y - b.y) * P.x + 1LL * (b.x - a.x) * P.y + 1LL * a.x * b.y - 1LL * a.y * b.x) > 0;
}
ll HullDif(int a, int b)
{
memset(vis, 0, sizeof(vis));
int head[2] = {0, 0};
for (int i = 1, p = 1; i > 0; i += (p = (i == n ? -p : p)))
{
int t = f(V[a], V[b], V[i]);
if (t) sol[0][V[i].id] = 'V';
else
sol[0][V[i].id] = 'I';
if (vis[t][i]) continue;
while (head[t] >= 2 && CrossProduct(V[st[t][head[t] - 1]], V[st[t][head[t]]], V[i]) <= 0)
vis[t][st[t][head[t] --]] = false;
st[t][++ head[t]] = i;
vis[t][i] = true;
}
ll A[2] = {0, 0};
if (head[0] < 3 || head[1] < 3 || (head[0] + head[1] != n))
return inf + 1;
if (sol[0][1] == 'V')
for (int i = 1; i <= n; ++ i)
if (sol[0][i] == 'V') sol[0][i] = 'I';
else sol[0][i] = 'V';
for (int t = 0; t < 2; ++ t)
{
st[t][head[t] + 1] = st[t][1];
for (int i = 1; i <= head[t]; ++ i)
A[t] += Det(V[st[t][i]], V[st[t][i + 1]]);
A[t] = abs(A[t]);
}
return abs(A[0] - A[1]);
}
bool lex()
{
for (int i = 1; i <= n; ++ i)
if (sol[0][i] != sol[1][i])
return sol[0][i] < sol[1][i];
return false;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++ i)
{
scanf("%d%d", &V[i].x, &V[i].y);
V[i].id = i;
}
sort(V + 1, V + n + 1);
ans = inf;
for (int a = 1; a < n; ++ a)
for (int b = 1 + a; b <= n; ++ b)
{
ll A = HullDif(a, b);
if (A < ans || (A == ans && lex()))
{
ans = A;
memcpy(sol[1], sol[0], sizeof(sol[0]));
}
}
if (ans & 1)
printf("%lld.5\n", ans / 2);
else
printf("%lld.0\n", ans / 2);
for (int i = 1; i <= n; ++ i)
printf("%c", sol[1][i]);
return 0;
}