Pagini recente » Cod sursa (job #2267984) | Cod sursa (job #1783431) | Cod sursa (job #1423649) | Cod sursa (job #2734583) | Cod sursa (job #1742549)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
ifstream cin("gradina.in");
ofstream cout("gradina.out");
const int MAXN = 255;
const long long INF = 0x3f3f3f3f3f3f3f3f;
struct Point{
int x;
int y;
int index;
bool operator < (const Point &other) const {
if (x == other.x)
return y < other.y;
return x < other.x;
}
};
Point v[1 + MAXN];
string bestRepartition, repartition;
int n;
int where[1 + MAXN];
long long Determinant(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);
}
vector<Point> ConvexHull(vector<Point> points) {
vector<Point> answer;
int Stack[1 + MAXN], top;
for (int j = 0; j <= 1; j++) {
top = 1;
Stack[0] = 0;
Stack[1] = 1;
for (int i = 2; i < points.size(); i++) {
while (top > 0 && Determinant(points[Stack[top - 1]], points[Stack[top]], points[i]) < 0)
top--;
top++;
Stack[top] = i;
}
for (int i = 0; i < top; i++)
answer.push_back(points[Stack[i]]);
reverse(points.begin(), points.end());
}
return answer;
}
long long Area(const vector<Point> &points) {
long long answer = 0;
for (int i = 1; i < points.size(); i++)
answer += llabs(Determinant(points[0], points[i - 1], points[i]));
return answer;
}
long long Difference(int first, int second) {
vector<Point> leftSet, rightSet, leftHull, rightHull;
for (int i = 1; i <= n; i++)
if (i == first || Determinant(v[first], v[second], v[i]) < 0) {
leftSet.push_back(v[i]);
where[i] = 0;
}
else {
rightSet.push_back(v[i]);
where[i] = 1;
}
leftHull = ConvexHull(leftSet);
if (leftHull.size() != leftSet.size())
return INF;
rightHull = ConvexHull(rightSet);
if (rightHull.size() != rightSet.size())
return INF;
for (int i = 1; i <= n; i++)
if (where[i] == 1)
repartition[v[i].index] = 'V';
else
repartition[v[i].index] = 'I';
if (repartition[1] == 'V')
for (int i = 1; i <= n; i++)
if (repartition[i] == 'V')
repartition[i] = 'I';
else
repartition[i] = 'V';
return llabs(Area(leftHull) - Area(rightHull));
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i].x >> v[i].y;
v[i].index = i;
}
sort(v + 1, v + n + 1);
long long answer = INF;
bestRepartition.assign(n + 1, 'V');
repartition.assign(n + 1, 'V');
for (int i = 1; i < n; i++)
for (int j = 1; j <= n; j++) {
long long current = Difference(i, j);
if (current < answer || (current == answer && bestRepartition > repartition)) {
answer = current;
bestRepartition = repartition;
}
}
cout << fixed << setprecision(1) << answer * 0.5 << "\n";
for (int i = 1; i <= n; i++)
cout << (char) bestRepartition[i];
cout << "\n";
return 0;
}