Pagini recente » Cod sursa (job #1689726) | Cod sursa (job #2874025) | Cod sursa (job #636995) | Monitorul de evaluare | Cod sursa (job #2000616)
#include <bits/stdc++.h>
#define maxN 252
#define inf 2000000000000000000LL
using namespace std;
FILE *fin = freopen("gradina.in", "r", stdin);
FILE *fout = freopen("gradina.out", "w", stdout);
/* ---------------------------------------- */
int n;
struct Point
{
int x, y, idx;
bool operator < (const Point &ot) const
{
if (x == ot.x)
return y < ot.y;
return x < ot.x;
}
} v[maxN];
/* ---------------------------------------- */
int P[2][maxN], st[maxN];
bool vis[maxN];
long long Area[2];
/* ---------------------------------------- */
long long ans;
char a[maxN], b[maxN];
bool Lex()
{
for (int i = 1; i <= n; ++ i)
if (a[i] != b[i])
return a[i] > b[i];
return 0;
}
bool 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) <= 0LL;
}
bool sep(int i, int j, int p)
{
long long a = v[i].y - v[j].x,
b = v[j].x - v[i].x,
c = 1LL * v[i].x * v[j].y - 1LL * v[i].y * v[j].x;
return 1LL * a * v[p].x + 1LL * b * v[p].y + c > 0;
}
void SepP(int i, int j)
{
P[0][0] = P[1][0] = 0;
for (int p = 1; p <= n; ++ p)
if (i != p && j != p)
{
if (sep(i, j, p))
{
P[0][++ P[0][0]] = p;
b[v[p].idx] = 'I';
}
else
{
P[1][++ P[1][0]] = p;
b[v[p].idx] = 'V';
}
}
else if (i == p)
{
P[0][++ P[0][0]] = p;
b[v[p].idx] = 'I';
}
else
{
P[1][++ P[1][0]] = p;
b[v[p].idx] = 'V';
}
}
int ConvexHull(int t)
{
st[0] = 2;
st[1] = 1;
st[2] = 2;
memset(vis, 0, sizeof(vis));
vis[2] = 1;
for (int i = 1, p = 1; i > 0; i += p)
{
if (!vis[i])
{
while (st[0] >= 2 && CrossProduct(v[P[t][st[st[0] - 1]]], v[P[t][st[st[0]]]], v[P[t][i]]))
vis[st[st[0] --]] = 0;
st[++ st[0]] = i;
vis[i] = 1;
}
if (i == P[t][0])
p = -1;
}
st[st[0]] = st[1];
Area[t] = 0;
for (int i = 1; i < st[0]; ++ i)
Area[t] += 1LL * v[P[t][st[i]]].x * v[P[t][st[i + 1]]].y - 1LL * v[P[t][st[i]]].y * v[P[t][st[i + 1]]].x;
Area[t] = abs(Area[t]);
return st[0] - 1;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++ i)
{
scanf("%d %d", &v[i].x, &v[i].y);
v[i].idx = i;
}
ans = inf;
sort(v + 1, v + n + 1);
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
if (i != j)
{
SepP(i, j);
if (P[0][0] < 3 || P[1][0] < 3)
continue;
for (int t = 0; t < 2; ++ t)
if (ConvexHull(t) != P[t][0])
break;
else if (t)
{
if ((ans > abs(Area[0] - Area[1])) || ((ans == abs(Area[0] - Area[1])) && Lex()))
{
memcpy(a, b, sizeof(b));
ans = abs(Area[0] - Area[1]);
}
}
}
for (int i = 1; i <= n; ++ i)
b[i] = 'I' + 'V' - a[i];
if (Lex())
memcpy(a, b, sizeof(b));
printf("%lld.%d\n", ans / 2, 5 * (ans % 2));
for (int i = 1; i <= n; ++ i)
printf("%c", a[i]);
return 0;
}