Pagini recente » Cod sursa (job #63660) | Cod sursa (job #3148294) | Cod sursa (job #1433121) | Cod sursa (job #3132543) | Cod sursa (job #728824)
Cod sursa(job #728824)
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define nmax 255
#define ll long long
struct punct
{
ll x, y;
int p;
} v[nmax];
vector <int> a, b;
char sv[nmax], solv[nmax];
int n, h, st[nmax], u[nmax];
ll sol;
int cmp (punct a, punct b)
{
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
long long semn (int i, int j, int k)
{
long long a, b, c;
a = v[i].y - v[j].y;
b = v[j].x - v[i].x;
c = (long long) v[i].x * v[j].y - (long long) v[j].x * v[i].y;
return a * v[k].x + b * v[k].y + c;
}
double convex_hull (vector <int> a)
{
int i, stp;
for (i=0; i < a.size(); i++) u[i] = 0;
u[0] = 1;
h = 1;
st[1] = 0;
stp = 1;
for (i=1; ; i+=stp)
{
if (!u[i])
{
while (semn (a[st[h-1]], a[st[h]], a[i]) < 0 && h > 1) u[st[h--]] = 0;
st[++h] = i;
u[i] = 1;
}
if (i == a.size()-1) stp = -1;
if (stp == -1 && !i) break;
}
if (h != a.size()) return -1;
st[h+1] = st[1];
ll area = 0;
for (i=1; i <= h; i++)
area += (long long) v[a[st[i]]].x * v[a[st[i+1]]].y - (long long) v[a[st[i+1]]].x * v[a[st[i]]].y;
if (area < 0) area = -area;
return area;
}
int main()
{
freopen ("gradina.in", "r", stdin);
freopen ("gradina.out", "w", stdout);
scanf ("%d", &n);
int i, j, k, ok;
char c1, c2;
double ar1, ar2;
ll d;
sol = 1<<30;
for (i=1; i <= n; i++)
{
scanf ("%lld %lld", &v[i].x, &v[i].y);
v[i].p = i;
}
sort (v+1, v+n+1, cmp);
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (i != j)
{
a.clear();
b.clear();
for (k=1; k<=n; k++)
if (k == i) a.push_back (k); else
if (k == j) b.push_back (k); else
if (semn (i, j, k) < 0) a.push_back (k); else
b.push_back (k);
if (a.size () < 3 || b.size() < 3) continue;
ar1 = convex_hull (a);
ar2 = convex_hull (b);
if (ar1 == -1 || ar2 == -1) continue;
d = ar1 - ar2;
if (d < 0) d = -d;
if (d <= sol)
{
if (a[0] == 1)
{
c1 = 'I';
c2 = 'V';
} else
{
c1 = 'V';
c2 = 'I';
}
for (k = 0; k < a.size(); k++) sv[v[a[k]].p] = c1;
for (k = 0; k < b.size(); k++) sv[v[b[k]].p] = c2;
ok = 0;
if (d != sol) ok = 1; else
for (k = 1; k <= n; k++)
if (sv[k] < solv[k])
{
ok = 1;
break;
}
if (ok)
for (k = 1; k <= n; k++) solv[k] = sv[k];
sol = d;
}
}
printf ("%.1lf\n", (double) sol *0.5);
for (i=1; i<=n; i++) printf ("%c",solv[i]);
}