Pagini recente » Cod sursa (job #1294809) | Cod sursa (job #2277240) | Cod sursa (job #1665166) | Cod sursa (job #1278786) | Cod sursa (job #3247482)
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()
using namespace std;
ifstream fin ("gradina.in");
ofstream fout ("gradina.out");
struct ura {
int x, y, idx;
};
int arie(ura a, ura b, ura c) {
return a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x;
}
double arie_poly(const vector<ura>& v) {
int n = sz(v);
double arie = 0;
for (int i = 0; i < n; ++i) {
int j = (i + 1) % n;
arie += v[i].x * v[j].y - v[i].y * v[j].x;
}
return abs(arie) / 2.0;
}
bool convex_hull(vector<ura>& v) {
if (sz(v) < 3) return false;
vector<ura> stk;
stk.push_back(v[0]);
for (int i = 1; i < sz(v); ++i) {
while (stk.size() > 1 && arie(stk[stk.size() - 2], stk.back(), v[i]) < 0)
stk.pop_back();
stk.push_back(v[i]);
}
v = stk;
return sz(stk) == sz(v);
}
void solve_testcase() {
int n;
fin >> n;
vector<ura> a(n);
for (int i = 0; i < n; ++i) {
fin >> a[i].x >> a[i].y;
a[i].idx = i;
}
sort(all(a), [](const ura &a, const ura &b) {
return make_pair(a.x, a.y) < make_pair(b.x, b.y);
});
double ans = 1e9;
string best(n, 'I');
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
vector<ura> u, v;
string cur(n, 'I');
for (int k = 0; k < n; ++k) {
if (k == i || k == j) continue;
if (arie(a[i], a[j], a[k]) < 0) {
v.push_back(a[k]);
cur[a[k].idx] = 'V';
} else {
u.push_back(a[k]);
}
}
u.push_back(a[i]);
v.push_back(a[j]);
if (convex_hull(u) && convex_hull(v)) {
double dif = abs(arie_poly(u) - arie_poly(v));
if (cur[0] == 'V') {
for (auto &it : cur)
it = (it == 'V' ? 'I' : 'V');
}
if (dif < ans || (dif == ans && cur < best)) {
ans = dif;
best = cur;
}
}
}
}
fout << fixed << setprecision(1) << ans << endl;
fout << best << endl;
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t = 1;
// fin >> t;
while (t--)
solve_testcase();
return 0;
}