Pagini recente » Cod sursa (job #3359648) | Cod sursa (job #3359667) | Cod sursa (job #3359655) | Cod sursa (job #3359654) | Cod sursa (job #3359656)
#include <bits/stdc++.h>
using namespace std;
#define USE_STD_IO 0
#if USE_STD_IO
#define fin cin
#define fout cout
#else
ifstream fin("gradina.in");
ofstream fout("gradina.out");
#endif
typedef bitset<252> Config;
struct Punct {
long long x, y;
} v[252];
struct Pilon {
Punct p;
long long i;
} cop[252];
long long n, i, j, k, mi;
Config rasp, ion;
long long top, stiv[252];
bool viz[252];
Punct stIon[252];
Punct stVas[252];
long long nrIon, nrVas;
static inline bool Cmp(Punct p1, Punct p2) {
return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
}
static inline bool CmpPilon(Pilon p1, Pilon p2) {
return Cmp(p1.p, p2.p);
}
static inline long long Det(Punct p1, Punct p2, Punct p3) {
return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}
static inline bool CmpConfig(const Config& a, const Config& b) {
int i = n - 1;
while(0 < i && a[i] == b[i]) i--;
return a[i] < b[i];
}
static inline long long ArieConvexHull(Punct p[], int m) {
if(3 > m) return 0;
stiv[0] = 0;
memset(viz, false, (m + 1) * sizeof(bool));
stiv[top = 1] = 1;
//viz[1] = 1;
int sens = 1;
for(int i = 2; i >= 1; i += sens) {
if(viz[i]) continue;
while(2 <= top && 0 > Det(p[i], p[stiv[top - 1]], p[stiv[top]])) {
viz[stiv[top--]] = false;
}
stiv[++top] = i;
viz[stiv[top]] = true;
if(m == i) sens = -1;
}
if(m + 1 != top) return 0;
long long arie = 0;
for(int i = 1; i <= m; i++) {
arie += p[stiv[i]].x * p[stiv[i + 1]].y - p[stiv[i]].y * p[stiv[i + 1]].x;
}
if(0 > arie) return -arie;
return arie;
}
int main() {
#if USE_STD_IO
ios_base::sync_with_stdio(false);
#endif // USE_STD_IO
fin.tie(NULL);
fout.tie(NULL);
fin >> n;
for(i = 1; i <= n; i++) {
fin >> v[i].x >> v[i].y;
cop[i].p = v[i];
cop[i].i = i;
}
sort(v + 1, v + n + 1, Cmp);
sort(cop + 1, cop + n + 1, CmpPilon);
mi = 1e17;
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
if(i == j) continue;
ion = 0;
nrIon = nrVas = 0;
for(k = 1; k <= n; k++) {
if(k == i) stIon[++nrIon] = v[k], ion[k - 1] = true;
else if(k == j) stVas[++nrVas] = v[k], ion[k - 1] = false;
else if(0 > Det(v[k], v[i], v[j])) {
stIon[++nrIon] = v[k], ion[k - 1] = true;
}
else {
stVas[++nrVas] = v[k], ion[k - 1] = false;
}
}
Config copIon = ion;
for(k = 0; k < n; k++) {
copIon[cop[k + 1].i - 1] = ion[k];
}
long long arie1 = ArieConvexHull(stIon, nrIon);
long long arie2 = ArieConvexHull(stVas, nrVas);
if(0 == arie1 || 0 == arie2) continue;
long long dif = arie1 - arie2;
if(0 > dif) dif = -dif;
if(dif < mi) {
mi = dif;
rasp = copIon;
}
else if(dif == mi && CmpConfig(copIon, rasp)) {
rasp = copIon;
}
}
}
fout << mi / 2 << '.' << (1 & mi ? '5' : '0') << '\n';
for(i = 0; i < n; i++) {
fout << (rasp[i] ? 'I' : 'V');
}
return 0;
}