Cod sursa(job #1742549)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 16 august 2016 16:39:35
Problema Gradina Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.27 kb
#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;
}