Cod sursa(job #3356371)

Utilizator rares89_Dumitriu Rares rares89_ Data 31 mai 2026 14:12:57
Problema Gradina Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.81 kb
#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;
}