Pagini recente » Cod sursa (job #866703) | Cod sursa (job #622251) | Cod sursa (job #1995405) | Cod sursa (job #805900) | Cod sursa (job #2711247)
#include <bits/stdc++.h>
#define NMAX 255
#define EPS 0.0000001
using namespace std;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
struct chestie
{
long long x, y;
int care;
} vec[NMAX], v1[NMAX], v2[NMAX], aux, st[NMAX];
int nr1, nr2, tip[NMAX], n;
double minn = LLONG_MAX / 2;
string sol;
double det(chestie x1, chestie x2, chestie x3)
{
return ((x1.x * x2.y) + (x1.y * x3.x) + (x2.x * x3.y) - (x3.x * x2.y) - (x1.y * x2.x) - (x1.x * x3.y));
}
inline bool cmp1(chestie a, chestie b)
{
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
inline bool cmp2(chestie a, chestie b)
{
return (det(aux, a, b) > 0.0);
}
bool checkPolig(chestie v[NMAX], int nr)
{
aux = v[1];
sort(v + 2, v + nr + 1, cmp2);
for(int i = 3; i <= nr; ++i)
if(det(v[i - 2], v[i - 1], v[i]) <= 0.0)
return 0;
return 1;
}
double ariaTr(chestie a, chestie b, chestie c)
{
a.x -= c.x;
b.x -= c.x;
a.y -= c.y;
b.y -= c.y;
return (double(a.x * b.y - b.x * a.y) / 2.0);
}
double getAria(chestie v[NMAX], int nr)
{
v[nr + 1] = v[1];
double rez = 0;
for(int i = 2; i <= nr; ++i)
rez += ariaTr(v[1], v[i], v[i + 1]);
return rez;
}
string getSol()
{
for(int i = 1; i <= nr1; ++i)
tip[v1[i].care] = 1;
for(int i = 1; i <= nr2; ++i)
tip[v2[i].care] = 2;
string rez = "";
int val = tip[1];
for(int i = 1; i <= n; ++i)
if(tip[i] == val)
rez += "I";
else rez += "V";
return rez;
}
int main()
{
fin >> n;
for(int i = 1; i <= n; ++i)
{
fin >> vec[i].x >> vec[i].y;
vec[i].care = i;
}
sort(vec + 1, vec + n + 1, cmp1);
for(int i = 1; i < n; ++i)
for(int j = i + 1; j <= n; ++j)
{
nr1 = nr2 = 0;
for(int k = 1; k <= n; ++k)
{
double val = det(vec[i], vec[j], vec[k]);
if(val < 0.0)
v1[++nr1] = vec[k];
else v2[++nr2] = vec[k];
}
if(nr1 >= 3 && nr2 >= 3 && checkPolig(v1, nr1) && checkPolig(v2, nr2))
{
double aria = abs(getAria(v1, nr1) - getAria(v2, nr2));
if(aria < minn)
minn = aria, sol = getSol();
else if(fabs(aria - minn) < EPS)
sol = min(sol, getSol());
}
}
fout << fixed << setprecision(1) << minn << '\n' << sol << '\n';
return 0;
}