Pagini recente » Cod sursa (job #746973) | Cod sursa (job #360802) | Cod sursa (job #3291099) | Cod sursa (job #226682) | Cod sursa (job #1886922)
#include <fstream>
#include <cstring>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin ("gradina.in");
ofstream fout ("gradina.out");
int n, a1, b1, a2, b2, V[260];
float dif, sol = 100000;
char S[260];
pair < pair < int, int >, int > P[260], A1[260], B1[260], A2[260], B2[260];
bool F[260];
int Cross_Product(pair < int, int > a, pair < int, int > b, pair < int, int > c)
{
return (c.first - a.first) * (b.second - a.second) - (c.second - a.second) * (b.first - a.first);
}
int Sup(pair < int, int > a, pair < int, int > b)
{
return (a.first * b.second) - (a.second * b.first);
}
float Modul(float a)
{
return (a < 0 ? -a : a);
}
float Verif(pair < pair < int, int >, int > C[], int nr)
{
memset(F, false, sizeof(F));
V[1] = 1;
V[2] = 2;
V[0] = 2;
F[1] = F[2] = true;
for (int i = 1, p = 1; i > 0; i += (p = (i == nr ? -p : p)))
{
if (!F[i])
{
while (V[0] > 1 && Cross_Product(C[V[V[0] - 1]].first, C[V[V[0]]].first, C[i].first) > 0)
{
F[V[V[0] --]] = false;
}
V[++ V[0]] = i;
F[i] = true;
}
}
float arie = 0;
V[nr + 1] = V[1];
for (int i = 1; i <= nr; i ++)
{
arie += Sup(C[V[i]].first, C[V[i + 1]].first);
}
return Modul(arie);
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i ++)
{
fin >> P[i].first.first >> P[i].first.second;
P[i].second = i;
}
sort(P + 1, P + 1 + n);
for (int i = 1; i <= n; i ++)
{
for (int j = i + 1; j <= n; j ++)
{
a1 = b1 = a2 = b2 = 0;
for (int k = 1; k <= n; k ++)
{
if (k == i)
{
A1[++ a1] = P[k];
B1[++ b1] = P[k];
}
else if (k == j)
{
A2[++ a2] = P[k];
B2[++ b2] = P[k];
}
else if (Cross_Product(P[i].first, P[k].first, P[j].first) > 0)
{
A1[++ a1] = P[k];
A2[++ a2] = P[k];
}
else
{
B1[++ b1] = P[k];
B2[++ b2] = P[k];
}
}
dif = Modul(Verif(A1, a1) - Verif(B2, b2));
if (dif < sol)
{
sol = dif;
for (int k = 1; k <= a1; k ++) S[A1[k].second] = 'I';
for (int k = 1; k <= b2; k ++) S[B2[k].second] = 'V';
}
dif = Modul(Verif(B1, b1) - Verif(A2, a2));
if (dif < sol)
{
sol = dif;
for (int k = 1; k <= b1; k ++) S[B1[k].second] = 'I';
for (int k = 1; k <= a2; k ++) S[A2[k].second] = 'V';
}
}
}
fout << fixed << setprecision(1) << sol / 2 << '\n';
fout << (S + 1) << '\n';
fout.close();
return 0;
}