Pagini recente » Cod sursa (job #3275262) | Cod sursa (job #2918601) | Cod sursa (job #611622) | Cod sursa (job #1191939) | Cod sursa (job #2610181)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("gradina.in");
ofstream g ("gradina.out");
struct NANI
{
int x, y;
};
NANI Ion[252];
NANI Vasile[252];
int st[252];
char ch[252];
NANI a[252];
double Min;
int n, aux;
int vfIon, vfVasile;
char S[252];
bool viz[252];
void Read ()
{
f >> n;
for (int i = 1; i <= n; i++)
{
f >> a[i].x >> a[i].y;
}
}
bool cmp (NANI a, NANI b)
{
if (a.x > b.x) return false;
if (a.x == b.x && a.y > b.y) return false;
return true;
}
int det (NANI a, NANI b, NANI c)
{
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
double convex_hull (NANI p[], int m)
{
double sol = 0;
for (int i = 1; i <= m; i++)
viz[i] = false;
st[1] = 1;
st[2] = 2;
viz[2] = true;
int vf = 2;
int poz = 2;
int pas = 1;
while (viz[1] == false)
{
while (viz[poz] == true)
{
poz += pas;
if (poz == m) pas = -1;
}
while (vf >= 2 && det(p[st[vf - 1]], p[st[vf]], p[poz]) < 0)
{
viz[st[vf]] = false;
vf--;
}
vf++;
st[vf] = poz;
viz[poz] = true;
}
for (int i = 1; i < vf; i++)
sol = sol + det(p[0], p[st[i]], p[st[i+1]]);
sol = sol / 2;
if (vf != m + 1)
{
aux = 0;
}
return sol;
}
void Solve ()
{
Min = 1000000000;
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
vfIon = 0;
vfVasile = 0;
if (i == 1 || det(a[1], a[i], a[j]) < 0)
{
for (int k = 1; k <= n; k++)
{
if (k == i || k == j || det(a[k], a[i], a[j]) < 0)
{
ch[k] = 'I';
vfIon++;
Ion[vfIon] = a[k];
}
else
{
ch[k] = 'V';
vfVasile++;
Vasile[vfVasile] = a[k];
}
}
}
else
{
for (int k = 1; k <= n; k++)
{
if (k == i || k == j || det(a[k], a[i], a[j]) < 0)
{
ch[k] = 'V';
vfVasile++;
Vasile[vfVasile] = a[k];
}
else
{
ch[k] = 'I';
vfIon++;
Ion[vfIon] = a[k];
}
}
}
if (vfIon < 3 || vfVasile < 3) continue;
sort(Ion + 1, Ion + vfIon + 1, cmp);
sort(Vasile + 1, Vasile + vfVasile + 1, cmp);
aux = 1;
double dif = abs(convex_hull(Ion, vfIon) - convex_hull(Vasile, vfVasile));
if (aux == 0) continue;
if (dif < Min)
{
Min = dif;
for (int k = 1; k <= n; k++) S[k] = ch[k];
}
}
}
g << setprecision(1) << fixed;
g << Min << '\n';
for (int i = 1; i <= n; i++)
g << S[i];
}
int main()
{
Read();
Solve();
return 0;
}