Pagini recente » Cod sursa (job #1265433) | Cod sursa (job #3213937) | Cod sursa (job #139703) | Cod sursa (job #585410) | Cod sursa (job #3356371)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
struct Point {
long long x, y;
};
long long cross(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
vector<Point> get_hull(vector<Point> pts) {
int n = pts.size(), k = 0;
if (n <= 2) return pts;
vector<Point> h(2 * n);
sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
});
for (int i = 0; i < n; ++i) {
while (k >= 2 && cross(h[k - 2], h[k - 1], pts[i]) <= 0) k--;
h[k++] = pts[i];
}
for (int i = n - 2, t = k + 1; i >= 0; i--) {
while (k >= t && cross(h[k - 2], h[k - 1], pts[i]) <= 0) k--;
h[k++] = pts[i];
}
h.resize(k - 1);
return h;
}
long long get_area_2(const vector<Point>& h) {
long long area = 0;
int n = h.size();
for (int i = 0; i < n; ++i) {
int j = (i + 1) % n;
area += h[i].x * h[j].y - h[j].x * h[i].y;
}
return abs(area);
}
int main() {
int n;
if (!(fin >> n)) return 0;
vector<Point> P(n);
for (int i = 0; i < n; ++i) {
fin >> P[i].x >> P[i].y;
}
long long min_diff_2 = -1;
string best_ans = "";
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) continue;
vector<Point> A, B;
string current_ans(n, ' ');
A.push_back(P[i]);
current_ans[i] = 'I';
B.push_back(P[j]);
current_ans[j] = 'V';
for (int k = 0; k < n; ++k) {
if (k == i || k == j) continue;
if (cross(P[i], P[j], P[k]) > 0) {
A.push_back(P[k]);
current_ans[k] = 'I';
} else {
B.push_back(P[k]);
current_ans[k] = 'V';
}
}
if (A.size() < 3 || B.size() < 3) continue;
if (get_hull(A).size() != A.size()) continue;
if (get_hull(B).size() != B.size()) continue;
long long areaA = get_area_2(get_hull(A));
long long areaB = get_area_2(get_hull(B));
long long diff_2 = abs(areaA - areaB);
if (min_diff_2 == -1 || diff_2 < min_diff_2) {
min_diff_2 = diff_2;
best_ans = current_ans;
} else if (diff_2 == min_diff_2) {
if (current_ans < best_ans) {
best_ans = current_ans;
}
}
}
}
fout << fixed << setprecision(1) << min_diff_2 / 2.0 << "\n";
fout << best_ans << "\n";
return 0;
}