Pagini recente » Cod sursa (job #859791) | Cod sursa (job #79849) | Cod sursa (job #2224693) | Cod sursa (job #1144992) | Cod sursa (job #1783630)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define MAXN 260
using namespace std;
struct coord
{
double x, y;
int ind;
bool operator()(coord e, coord f)
{
if (e.x != f.x) return e.x < f.x;
return e.y < f.y;
}
};
coord a[MAXN];
int n;
double EPS = 0.0000007;
double dabs(double e)
{
if (e < 0) return -e;
return e;
}
double eq(double e, double f)
{
return e-f > -EPS && e-f < EPS;
}
double det(coord e1, coord e2, coord e3)
{
return e1.x*e2.y + e2.x*e3.y + e3.x*e1.y - e3.x*e2.y - e2.x*e1.y - e1.x*e3.y;
}
void read()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lf %lf", &a[i].x, &a[i].y);
a[i].ind = i;
}
sort(a+1, a+1+n, coord());
}
vector<coord> poly;
char sol[MAXN], crt[MAXN];
void buildCrt()
{
for (int i = 1; i <= n; i++)
crt[i] = 'I';
for (coord c : poly)
crt[c.ind] = 'V';
if (crt[1] == 'V')
for (int i = 1; i <= n; i++)
crt[i] = (crt[i] == 'V' ? 'I' : 'V');
}
void add(vector<coord> &sc, coord c)
{
while (sc.size() >= 2 && det(sc[sc.size()-2], sc.back(), c) > 0)
sc.pop_back();
sc.push_back(c);
}
int buildPoly(coord e, coord f, int sus)
{
poly.clear();
for (int i = 1; i <= n; i++)
if ((det(e, f, a[i]) >= 0) == sus)
poly.push_back(a[i]);
vector<coord> scoica;
for (int i = 0; i < poly.size(); i++)
add(scoica, poly[i]);
for (int i = poly.size()-2; i >= 0; i--)
add(scoica, poly[i]);
scoica.pop_back();
if (poly.size() != scoica.size())
return 0;
for (int i = 0; i < poly.size(); i++)
poly[i] = scoica[i];
return 1;
}
double arie()
{
if (poly.size() == 0) return 0;
double to = 0;
coord au;
au.x = 0, au.y = 0;
for (int i = 0; i < poly.size()-1; i++)
to += det(au, poly[i], poly[i+1]);
to += det(au, poly.back(), poly.front());
to /= -2;
while (to < 0);
return to;
}
int better()
{
for (int i = 1; i <= n; i++)
if (crt[i] < sol[i])
return 1;
else if (sol[i] < crt[i])
return 0;
}
void solve()
{
double best = 5e300;
for (int i = 1; i <= n; i++)
for (int j = i+1; j <= n; j++) {
int ok = 1;
ok &= buildPoly(a[i], a[j], 1);
double a1 = arie();
ok &= buildPoly(a[i], a[j], 0);
if (!ok) continue;
double a2 = arie();
double dif = dabs(a1-a2);
buildCrt();
if (dif < best || eq(dif, best) && better()) {
best = dif;
for (int i = 1; i <= n; i++)
sol[i] = crt[i];
}
}
printf("%f\n", best);
printf("%s", sol+1);
}
int main()
{
freopen("gradina.in", "r", stdin);
freopen("gradina.out", "w", stdout);
read();
solve();
return 0;
}