Pagini recente » Cod sursa (job #1739834) | Cod sursa (job #2070377) | Cod sursa (job #2528172) | Cod sursa (job #2788078) | Cod sursa (job #2609894)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f ("gradina.in");
ofstream g ("gradina.out");
struct punct
{
int x, y;
};
punct a[300];
int N;
punct ion[300];
punct vasile[300];
char car[300], sol[300];
bool viz[300];
int st[300];
void Read ()
{
f >> N;
for (int i = 1; i <= N; ++i)
f >> a[i].x >> a[i].y;
}
bool cmp (punct a, punct b)
{
if (a.x > b.x) return false;
if (a.x == b.x && a.y > b.y) return false;
return true;
}
int det (punct a, punct b, punct c)
{
return (c.y - a.y) * (b.x - a.x) - (c.x - a.x) * (b.y - a.y);
}
double Area (punct p[], int N)
{
double sol = 0;
sort(p+1, p+N+1, cmp);
for (int i = 1; i <= N; ++i)
viz[i] = false;
st[1] = 1;
st[2] = 2;
viz[2] = true;
int vf = 2;
int poz = 2, pas = 1;
while (viz[1] == false)
{
while (viz[poz] == true)
{
poz += pas;
if (poz == N) pas = -1;
}
while (vf >= 2 && det(p[st[vf-1]], p[st[vf]], p[poz]) < 0)
{
viz[st[vf]] = 0;
-- vf;
}
++ vf;
st[vf] = poz;
viz[poz] = 1;
}
for (int i = 1; i < vf; ++i)
sol = sol + det(p[0], p[st[i]], p[st[i+1]]);
sol = sol / 2;
return sol;
}
void Solve()
{
double Min = 1000000000;
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j)
{
if (i == j) continue;
int nr_ion = 0, nr_vasile = 0;
for (int k = 1; k <= N; ++k)
if (det(a[i], a[j], a[k]) <= 0)
{
vasile[++nr_vasile] = a[k];
car[k] = 'V';
}
else
{
ion[++nr_ion] = a[k];
car[k] = 'I';
}
if (nr_vasile < 3 || nr_ion < 3) continue;
double arie_ion = Area(ion, nr_ion);
double arie_vasile = Area(vasile, nr_vasile);
double dif = abs(arie_ion - arie_vasile);
if (dif < Min)
{
Min = dif;
for (int k = 1; k <= N; ++k)
sol[k] = car[k];
}
else if (dif == Min)
{
bool ok = 1;
for (int k = 1; k <= N; ++k)
if (sol[k] > car[k]) break;
else if (sol[k] < car[k])
{
ok = 0;
break;
}
if (ok == 1)
{
for (int k = 1; k <= N; ++k)
sol[k] = car[k];
}
}
}
g << Min << '\n';
for (int i = 1; i <= N; ++i)
g << sol[i];
}
int main()
{
Read();
Solve();
return 0;
}