Pagini recente » Cod sursa (job #1540911) | Cod sursa (job #1557469) | Cod sursa (job #2305116) | Cod sursa (job #1779144)
#include <fstream>
#include <algorithm>
#include <string>
#include <cstring>
#include <iostream>
#include <iomanip>
using namespace std;
ifstream fin ("gradina.in"); ofstream fout ("gradina.out");
const int nmax = 250;
const long long inf = (1LL << 60);
int n;
long long arie;
string s;
struct pct{
int x, y;
} centru, v[nmax + 1], a[nmax + 1], b[nmax + 1];
inline bool cmp (pct x, pct y) {
return 1LL * x.y * y.x <
1LL * y.y * x.x;
}
inline int ccw (pct x, pct y, pct z) {
long long ans = (1LL * x.x * y.y - 1LL * x.y * y.x +
1LL * y.x * z.y - 1LL * y.y * z.x +
1LL * z.x * x.y - 1LL * z.y * x.x);
if (ans > 0) return 1;
if (ans == 0) return 0;
return -1;
}
long long calc_arie (pct x[], int lg) {
long long ans = 0;
for (int i = 0; i < lg - 1; ++ i) {
ans += (1.0 * x[ i ].x * x[i + 1].y - 1.0 * x[i + 1].x * x[ i ].y);
}
ans += (1.0 * x[lg - 1].x * x[ 0 ].y - 1.0 * x[ 0 ].x * x[lg - 1].y);
if (ans < 0) ans = -ans;
return ans;
}
bool infasuratoare (pct x[], int lg) {
int ind = 0;
for (int i = 1; i < lg; ++ i) {
if (x[ ind ].x > x[ i ].x) {
ind = i;
} else if (x[ ind ].x == x[ i ].x && x[ ind ].y > x[ i ].y) {
ind = i;
}
}
swap(x[ 0 ], x[ ind ]);
centru = x[ 0 ];
for (int i = 0; i < lg; ++ i) {
x[ i ].x -= centru.x;
x[ i ].y -= centru.y;
}
sort(x + 1, x + lg, cmp);
for (int i = 2; i < lg; ++ i) {
if (ccw(x[i - 2], x[i - 1], x[ i ]) == -1) {
return 0;
}
}
return 1;
}
void solve (int x, int y) {
string aux;
aux.resize( n );
int lga, lgb;
lga = lgb = 0;
for (int i = 0; i < n; ++ i) {
int unde = ccw(v[ x ], v[ y ], v[ i ]);
if (unde > 0 || i == x) {
a[ lga ++ ] = v[ i ];
aux[ i ] = 'I';
} else {
b[ lgb ++ ] = v[ i ];
aux[ i ] = 'V';
}
}
if (lga < 3 || lgb < 3) return ;
if (infasuratoare(a, lga) == 0 || infasuratoare(b, lgb) == 0) return ;
long long dif = calc_arie(a, lga) - calc_arie(b, lgb);
if (dif < 0) dif = -dif;
if (aux[ 0 ] == 'V') {
for (int i = 0; i < n; ++ i) {
if (aux[ i ] == 'I') aux[ i ] = 'V';
else aux[ i ] = 'I';
}
}
if (dif < arie) {
arie = dif;
s = aux;
} else if (dif == arie && aux < s) {
s = aux;
}
}
int main() {
fin >> n;
for (int i = 0; i < n; ++ i) {
fin >> v[ i ].x >> v[ i ].y;
}
arie = inf;
for (int i = 0; i < n; ++ i) {
for (int j = i + 1; j < n; ++ j) {
solve(i, j);
}
}
fout << setprecision( 1 ) << fixed;
fout << 0.5 * arie << "\n" << s;
fin.close();
fout.close();
return 0;
}