Cod sursa(job #2641254)

Utilizator trifangrobertRobert Trifan trifangrobert Data 10 august 2020 19:26:57
Problema Gradina Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.5 kb
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>

using namespace std;

const int NMAX = 255;

int det(pair <int, int> a, pair <int, int> b, pair <int, int> c)
{
    return (1LL * a.first * b.second + 1LL * b.first * c.second + 1LL * c.first * a.second) - (1LL * b.second * c.first + 1LL * c.second * a.first + 1LL * a.second * b.first);
}

vector < pair <int, int> > ConvexHull(vector <pair <int, int> > hull)
{
    vector < pair <int, int> > stk;
    stk.push_back(hull[0]);
    for (int i = 1; i < hull.size(); ++i)
    {
        while (stk.size() >= 2 && det(stk[stk.size() - 2], stk[stk.size() - 1], hull[i]) < 0)
            stk.pop_back();
        stk.push_back(hull[i]);
    }
    return stk;
}

long double Area(vector <pair <int, int> > p)
{
    long double area = 1LL * p[0].second * p.back().first - 1LL * p[0].first * p.back().second;
    for (int i = 0; i < p.size() - 1; ++i)
        area += 1LL * p[i].first * p[i + 1].second - 1LL * p[i].second * p[i + 1].first;
    area /= 2;
    return area;
}

int Solve(vector <int> p, vector <pair <int, int> > points)
{
    if (p.size() < 3)
        return -1;
    sort(p.begin(), p.end(), [&](int i, int j)
        {
            if (points[i].first == points[j].first)
                return points[i].second < points[j].second;
            return points[i].first < points[j].first;
        });
    vector <pair <int, int> > underHull;
    vector <pair <int, int> > aboveHull;
    underHull.push_back(points[p[0]]);
    aboveHull.push_back(points[p[0]]);
    for (int i = 1; i < p.size() - 1; ++i)
    {
        if (det(points[p[0]], points[p[i]], points[p.back()]) >= 0)
            underHull.push_back(points[p[i]]);
        else
            aboveHull.push_back(points[p[i]]);
    }
    underHull.push_back(points[p.back()]);
    aboveHull.push_back(points[p.back()]);
    reverse(aboveHull.begin(), aboveHull.end());
    int szUnderHull = underHull.size();
    int szAboveHull = aboveHull.size();
    underHull = ConvexHull(underHull);
    aboveHull = ConvexHull(aboveHull);
    if (underHull.size() != szUnderHull || aboveHull.size() != szAboveHull)
        return -1;
    underHull.pop_back();
    aboveHull.pop_back();
    vector <pair <int, int> > hull;
    for (auto& i : underHull)
        hull.push_back(i);
    for (auto& i : aboveHull)
        hull.push_back(i);
    if (hull.size() == p.size())
        return Area(hull);
    return -1;
}

int main()
{
    ifstream fin("gradina.in");
    ofstream fout("gradina.out");
    int N;
    fin >> N;
    vector < pair <int, int> > points(N);
    for (int i = 0; i < N; ++i)
        fin >> points[i].first >> points[i].second;
    long double answerDiff = (1LL << 60);
    string answer(N, '0');
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            if (i != j)
            {
                vector <int> p1, p2;
                for (int k = 0; k < N; ++k)
                {
                    if (i == k)
                        p1.push_back(k);
                    else if (j == k)
                        p2.push_back(k);
                    else
                    {
                        if (det(points[i], points[k], points[j]) >= 0)
                            p1.push_back(k);
                        else
                            p2.push_back(k);
                    }
                }
                long double area1 = Solve(p1, points);
                long double area2 = Solve(p2, points);
                if (area1 != -1 && area2 != -1)
                {
                    long double diff = abs(area1 - area2);
                    string aux(N, 'V');
                    for (auto& k : p1)
                        aux[k] = 'I';
                    if (aux[0] == 'V')
                    {
                        for (auto& k : aux)
                        {
                            if (k == 'I')
                                k = 'V';
                            else
                                k = 'I';
                        }
                    }
                    if (diff < answerDiff || (diff == answerDiff && aux < answer))
                    {
                        answerDiff = diff;
                        answer = aux;
                    }
                }
            }
    fout << setprecision(1) << fixed;
    fout  << answerDiff << "\n";
    fout << answer << "\n";
    fin.close();
    fout.close();
    return 0;
}