Cod sursa(job #3222570)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 10 aprilie 2024 21:29:12
Problema Gradina Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.43 kb
//#include <iostream>
#include <fstream>
#include <set>
#include <cmath>
#include <stack>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <unordered_map>
#include <map>
#define ll long long

using namespace std;

const int NMAX = 250;
const ll INF = 1000000000000000000;

ifstream cin("gradina.in");
ofstream cout("gradina.out");

struct Point
{
    int x, y, pos;
    void Read(int i)
    {
        cin >> x >> y;
        pos = i - 1;
    }
};

int n, indH, indL, indR;
Point points[NMAX + 1], hull_left[NMAX + 1], hull_right[NMAX + 1];
Point left_points[NMAX + 1], right_points[NMAX + 1];
double min_dif;
string curent_solution, solution;

ll CrossProduct(Point p1, Point p2, Point p3)
{
    return (ll)(p2.x - p1.x) * (p3.y - p1.y) - (ll)(p3.x - p1.x) * (p2.y - p1.y);
}

bool cmpP(const Point& a, const Point& b)
{
    if (a.x < b.x)
        return true;
    if (a.x == b.x && a.y < b.y)
        return true;
    return false;
}

int GetSizeHull(Point hull[], Point points[], int indP)
{
    indH = 0;
    int lim = 2;
    for (int i = 1; i <= indP; i++)
    {
        while (indH >= lim && CrossProduct(hull[indH - 1], hull[indH], points[i]) >= 0)
            indH--;
        hull[++indH] = points[i];
    }
    indH--;
    lim += indH;
    for (int i = indP; i >= 1; i--)
    {
        while (indH >= lim && CrossProduct(hull[indH - 1], hull[indH], points[i]) >= 0)
            indH--;
        hull[++indH] = points[i];
    }
    indH--;
    return indH;
}

double GetArea(Point points[], int indP)
{
    double area = 0;
    for (int i = 1; i <= indP; i++)
        area += CrossProduct({ 0, 0 }, points[i], points[i == indP ? 1 : i + 1]);
    return abs(area) / 2.0;
}

double GetDifference(int first_fixed, int second_fixed)
{
    indL = indR = 0;
    for (int i = 1; i <= n; i++)
    {
        if (i == first_fixed || CrossProduct(points[first_fixed], points[second_fixed], points[i]) < 0)
        {
            left_points[++indL] = points[i];
            curent_solution[points[i].pos] = 'I';
        }
        else
        {
            right_points[++indR] = points[i];
            curent_solution[points[i].pos] = 'V';
        }
    }

    int hull_size_left = GetSizeHull(hull_left, left_points, indL);
    int hull_size_right = GetSizeHull(hull_right, right_points, indR);
    if (hull_size_left != indL || hull_size_right != indR)
        return INF;

    if (curent_solution[0] == 'V')
        for (int i = 0; i < n; i++)
            curent_solution[i] = (curent_solution[i] == 'V' ? 'I' : 'V');

    double area_left = GetArea(hull_left, indL);
    double area_right = GetArea(hull_right, indR);
    return abs(area_left - area_right);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++)
        points[i].Read(i);

    sort(points + 1, points + n + 1, cmpP);

    min_dif = INF;
    curent_solution.resize(n);
    solution.resize(n);
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            double dif = GetDifference(i, j);
            if (dif < min_dif || (dif == min_dif && curent_solution < solution))
            {
                min_dif = dif;
                solution = curent_solution;
            }
        }
    }

    cout << fixed << setprecision(1) << min_dif << '\n' << solution;

    return 0;
}