Pagini recente » Cod sursa (job #2356678) | Cod sursa (job #2358807) | Cod sursa (job #3187969) | Cod sursa (job #2324956) | Cod sursa (job #325604)
Cod sursa(job #325604)
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
#define sz(c) int((c).size())
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define inf 1000000000 //un miliard
#define Nmax 256
struct punct {
int x, y, z;
bool operator < (const punct& p) const {
return x != p.x ? x < p.x : y < p.y;
}
};
int n;
punct pt[Nmax];
vector<int> v, u;
vector<char> aux;
int best = inf;
vector<char> ret;
char viz[Nmax];
int st[Nmax], cnt;
void readdata()
{
freopen("gradina.in", "r", stdin);
freopen("gradina.out", "w", stdout);
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d %d", &pt[i].x, &pt[i].y);
pt[i].z = i;
}
}
int arie(vector<int> &v)
{
int i, ret = 0;
for (i = 0; i < sz(v)-1; ++i)
ret += pt[v[i]].x * pt[v[i+1]].y - pt[v[i]].y * pt[v[i+1]].x;
return abs(ret);
}
int sign(int a, int b, int c)
{
return (pt[a].x-pt[c].x)*(pt[b].y-pt[c].y) - (pt[b].x-pt[c].x)*(pt[a].y-pt[c].y) < 0;
}
int convex_hull(vector<int> &v)
{
int i, p = 1, nr = sz(v);
vector<int> aux;
if (nr < 3) return 0;
memset(viz, 0, sizeof(viz));
st[cnt = 0] = 0;
for (i = 1; i >= 0; i += (p = (i == sz(v)-1 ? -p : p)))
if (!viz[i])
{
while (cnt >= 1 && sign( v[i], v[st[cnt]], v[st[cnt-1]] ))
viz[ st[cnt--] ] = 0;
viz[ st[ ++cnt ] = i ] = 1;
}
for (i = 0; i <= cnt; ++i)
aux.pb( v[ st[i] ]);
v = aux;
return cnt == nr;
}
void eval(vector<int> &v, vector<int> &u)
{
int tmp, i;
if (convex_hull(u) && convex_hull(v))
{
tmp = abs(arie(v) - arie(u));
if (tmp > best) return;
for (i = 0; i < sz(v)-1; ++i)
aux[ pt[v[i]].z ] = 'I';
for (i = 0; i < sz(u)-1; ++i)
aux[ pt[u[i]].z ] = 'V';
if (aux[0] == 'V')
for (i = 0; i < n; ++i)
if (aux[i] == 'I') aux[i] = 'V';
else aux[i] = 'I';
if (tmp < best)
{
best = tmp;
ret = aux;
}
if (aux < ret) ret = aux;
}
}
void solve()
{
int i, j, k;
sort(pt, pt+n);
aux.resize(n);
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
if (i != j)
{
v.clear(); u.clear();
for (k = 0; k < n; ++k)
if (k != i && k != j)
if (sign(k, j, i)) v.pb(k);
else u.pb(k);
else
if (k == i) v.pb(k);
else u.pb(k);
eval(v, u);
}
}
void writedata()
{
printf("%.1lf\n", (double)best/(double)2);
for (int i = 0; i < sz(ret); ++i)
printf("%c", ret[i]);
}
int main()
{
readdata();
solve();
writedata();
return 0;
}