Cod sursa(job #1700006)

Utilizator sucureiSucureiRobert sucurei Data 9 mai 2016 08:21:38
Problema Gradina Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.5 kb
#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';
    }
    string other = solution;
    for (int i = 0; i < static_cast<int>(solution.size()); ++ i) {
        other[i] = (other[i] == 'I') ? 'V' : 'I';
    }
    if (solution > other) {
        solution = other;
    }
    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;
}