Pagini recente » Cod sursa (job #423607) | Cod sursa (job #1167399) | Cod sursa (job #524225) | Cod sursa (job #349609) | Cod sursa (job #863699)
Cod sursa(job #863699)
#include <cstdio>
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <cstring>
#include <ctime>
#include <cassert>
#include <utility>
using namespace std;
#define INF 1e15
#define MAXN 255
struct Point {
int x, y;
};
int N;
Point P[MAXN];
int idx[MAXN];
int FIRST;
int st[MAXN];
int head;
bool v[MAXN];
char distr1[MAXN], distr2[MAXN];
string minDistr;
long long crossProduct(const Point &A, const Point &B, const Point &C) {
return (long long)(B.x - A.x) * (C.y - A.y) - (long long)(B.y - A.y) * (C.x - A.x);
}
bool cmp(const int &A, const int &B) {
return P[A].y < P[B].y || (P[A].y == P[B].y && P[A].x < P[B].x);
}
void convexHull(vector<int> &pts, vector<int> &R) {
if(pts.size() < 3)
return;
memset(v, false, sizeof(v));
st[0] = pts[0];
st[1] = pts[1];
v[pts[1]] = true;
head = 1;
for(size_t i = 2; i < pts.size(); i++) {
if(v[i]) continue;
while(head >= 1 && crossProduct(P[st[head - 1]], P[st[head]], P[pts[i]]) < 0) {
v[st[head]] = false;
head--;
}
v[pts[i]] = true;
st[++head] = pts[i];
}
for(int i = (int)pts.size() - 1; i >= 0; i--) {
if(v[pts[i]]) {
v[pts[i]] = false;
continue;
}
while(head >= 1 && crossProduct(P[st[head - 1]], P[st[head]], P[pts[i]]) < 0) {
v[st[head]] = false;
head--;
}
st[++head] = pts[i];
}
for(int i = 0; i < head; i++)
R.push_back(st[i]);
}
long long ariePoligon(vector<int> &pts) {
long long ret = 0;
for(size_t i = 1; i + 1 < pts.size(); i++) {
long long cp = crossProduct(P[pts[0]], P[pts[i]], P[pts[i + 1]]);
ret += cp;
}
return abs(ret);
}
string getDistr(vector<int> P[2]) {
for(int i = 0; i < 2; i++)
for(size_t j = 0; j < P[i].size(); j++) {
if(i == 0) {
distr1[P[i][j]] = 'I';
distr2[P[i][j]] = 'V';
}
else {
distr1[P[i][j]] = 'V';
distr2[P[i][j]] = 'I';
}
}
string v1(distr1);
string v2(distr2);
return min(v1, v2);
}
int main() {
freopen("gradina.in", "r", stdin);
freopen("gradina.out","w", stdout);
scanf("%d", &N);
for(int i = 0; i < N; i++)
scanf("%d %d", &P[i].x, &P[i].y);
for(int i = 0; i < N; i++)
idx[i] = i;
sort(idx, idx + N, cmp);
long long minDiff = INF;
for(int x = 0; x < N; x++)
for(int y = 0; y < N; y++)
if(x != y) {
vector<int> sp[2];
for(int i = 0; i < N; i++) {
if(i == x)
sp[0].push_back(idx[x]);
else if(i == y)
sp[1].push_back(idx[y]);
else {
long long cp = crossProduct(P[idx[x]], P[idx[y]], P[idx[i]]);
int side = (cp > 0);
sp[side].push_back(idx[i]);
}
}
vector<int> inf[2];
convexHull(sp[0], inf[0]);
if(sp[0].size() != inf[0].size())
continue;
convexHull(sp[1], inf[1]);
if(sp[1].size() != inf[1].size())
continue;
long long arie[2];
arie[0] = ariePoligon(inf[0]);
arie[1] = ariePoligon(inf[1]);
long long diff = arie[0] - arie[1];
if(diff < 0)
diff = -diff;
if(diff < minDiff) {
minDiff = diff;
minDistr = getDistr(inf);
}
else if(diff == minDiff) {
string s = getDistr(inf);
if(s < minDistr)
minDistr = s;
}
}
printf("%.1lf\n", (double)minDiff / 2.0);
printf("%s\n", minDistr.c_str());
return 0;
}