Pagini recente » Cod sursa (job #1636668) | Cod sursa (job #2499678) | Cod sursa (job #1731868) | Cod sursa (job #6467) | Cod sursa (job #1724345)
#include <bits/stdc++.h>
using namespace std;
const int N_MAX = 256;
const int64_t INF = 0x3f3f3f3f3f3f3f3f;
struct Point {
int x, y, id;
bool operator <(const Point &o) const { return (x == o.x ? y < o.y : x < o.x); }
};
int N;
Point P[N_MAX];
bool preSol[N_MAX];
string Sol, bestSol;
int64_t Det(const Point &A, const Point &B, const Point &C) {
return 1LL * (B.x - A.x) * (C.y - A.y) - 1LL * (B.y - A.y) * (C.x - A.x);
}
int64_t getArea(const vector<Point> &P) {
int64_t Area = 0;
for(int i = 1; i < P.size(); i++) Area += llabs(Det(P[0], P[i - 1], P[i]));
return Area;
}
vector<Point> getConvex(vector<Point> &P) {
vector<Point> H;
int Stack[N_MAX], Top;
for(int j = 0; j < 2; j++) {
Stack[0] = 0;
Stack[1] = 1;
Top = 1;
for(int i = 2; i < P.size(); i++) {
while(Top > 0 && Det(P[Stack[Top - 1]], P[Stack[Top]], P[i]) < 0) Top--;
Stack[++Top] = i;
}
for(int i = 0; i < Top; i++) H.push_back(P[Stack[i]]);
reverse(P.begin(), P.end());
}
return H;
}
int64_t getDifference(int fixedFirst, int fixedSecond) {
vector<Point> leftSide, rightSide, leftConvex, rightConvex;
for(int i = 1; i <= N; i++) {
if(i == fixedFirst || Det(P[fixedFirst], P[fixedSecond], P[i]) < 0) {
leftSide.push_back(P[i]);
preSol[i] = 0;
} else {
rightSide.push_back(P[i]);
preSol[i] = 1;
}
}
leftConvex = getConvex(leftSide);
if(leftSide.size() != leftConvex.size()) return INF;
rightConvex = getConvex(rightSide);
if(rightSide.size() != rightConvex.size()) return INF;
for(int i = 1; i <= N; i++) Sol[P[i].id] = (preSol[i] == preSol[0] ? 'I' : 'V');
return llabs(getArea(leftConvex) - getArea(rightConvex));
}
int main() {
freopen("gradina.in", "r", stdin);
freopen("gradina.out", "w", stdout);
scanf("%d", &N);
for(int i = 1; i <= N; i++) {
scanf("%d %d", &P[i].x, &P[i].y);
P[i].id = i;
}
sort(P+1, P+N+1);
int64_t minDiff = INF;
int bestFirst, bestSecond;
bestSol.assign(N + 1, 'V');
Sol.assign(N + 1, 'V');
for(int i = 1; i <= N; i++) {
for(int j = i + 1; j <= N; j++) {
int64_t Diff = getDifference(i, j);
if(minDiff > Diff || (minDiff == Diff && bestSol > Sol)) {
minDiff = Diff;
bestSol = Sol;
}
}
}
printf("%.1f\n", 0.5 * minDiff);
for(int i = 1; i <= N; i++) printf("%c", bestSol[i]);
printf("\n");
return 0;
}