Pagini recente » Cod sursa (job #1280795) | Cod sursa (job #2633851) | Cod sursa (job #2067555) | Cod sursa (job #1702365) | Cod sursa (job #1266092)
#include <cmath>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 256;
struct Point {
int index, x, y;
inline bool operator < (const Point & other) const {
return x < other.x || (x == other.x && y < other.y);
}
} a[MAX_N];
vector<Point> v1, v2;
int n;
string solution, best;
inline long long semn(const Point &a, const Point &b, const Point &c) {
return 1LL * (b.x - a.x) * (c.y - b.y) - 1LL * (b.y - a.y) * (c.x - b.x);
}
inline bool convex_hull(vector<Point> &v) {
if (static_cast<int>(v.size()) < 3) {
return false;
}
vector<Point> answer(1, v[0]);
answer.push_back(v[1]);
for (int i = 2; i < static_cast<int>(v.size()); ++ i) {
while (static_cast<int>(answer.size()) >= 2 && semn(answer[answer.size() - 2], answer[answer.size() - 1], v[i]) < 0) {
answer.pop_back();
}
answer.push_back(v[i]);
}
answer.push_back(v[v.size() - 2]);
for (int i = v.size() - 3; i >= 0; -- i) {
while (static_cast<int>(answer.size()) >= 2 && semn(answer[answer.size() - 2], answer[answer.size() - 1], v[i]) < 0) {
answer.pop_back();
}
answer.push_back(v[i]);
}
if (answer.size() == v.size() + 1) {
v = answer;
return true;
}
return false;
}
inline long long LLabs(long long x) {
return x < 0 ? -x : x;
}
long long solve(int x, int y) {
v1.clear(); v2.clear();
for (int i = 1; i <= n; ++ i) {
if (i == x) {
v1.push_back(a[i]);
} else if (i == y) {
v2.push_back(a[i]);
} else if (semn(a[min(x, y)], a[max(x, y)], a[i]) < 0) {
v1.push_back(a[i]);
} else {
v2.push_back(a[i]);
}
}
if (!convex_hull(v1) || !convex_hull(v2)) {
return 1LL << 60;
}
for (vector<Point> :: iterator it = v1.begin(); it != v1.end(); ++ it) {
solution[it->index - 1] = 'I';
}
for (vector<Point> :: iterator it = v2.begin(); it != v2.end(); ++ it) {
solution[it->index - 1] = 'V';
}
long long answer = 0;
for (int i = 0; i + 1 < static_cast<int>(v1.size()); ++ i) {
answer += 1LL * v1[i].x * v1[i + 1].y - 1LL * v1[i].y * v1[i + 1].x;
}
for (int i = 0; i + 1 < static_cast<int>(v2.size()); ++ i) {
answer -= 1LL * v2[i].x * v2[i + 1].y - 1LL * v2[i].y * v2[i + 1].x;
}
return LLabs(answer);
}
int main() {
ifstream fin("gradina.in");
ofstream fout("gradina.out");
long long diff = 1LL << 50;
fin >> n; solution.assign(n, 'W'); best.assign(n, 'W');
for (int i = 1; i <= n; ++ i) {
fin >> a[i].x >> a[i].y;
a[i].index = i;
}
sort (a + 1, a + n + 1);
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
if (i != j) {
long long answer = solve(i, j);
if (diff > answer || (answer == diff && solution < best)) {
diff = answer;
best = solution;
}
}
}
}
fout << fixed << setprecision(1) << diff * 0.5 << "\n";
fout << best << "\n";
return 0;
}