Cod sursa(job #2370245)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 6 martie 2019 11:19:50
Problema Gradina Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.41 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

struct Punct
{
    int x, y, ind;
    bool operator<(const Punct &that)
    {
        if(x == that.x)
            return y < that.y;
        return x < that.x;
    }
};

inline long long cp(const Punct &O, const Punct &A, const Punct &B)
{
    return 1LL * (A.x - O.x) * (B.y - O.y) - 1LL * (A.y - O.y) * (B.x - O.x);
}

//Daca e convex, sorteaza v trigonometric
bool convex(vector<Punct> &v)
{
    vector<bool> viz(v.size(), false);
    vector<int> st(v.size());
    int top = -1;
    for(int i = 0, p = 1; i >= 0; i += p)
    {
        if(viz[i])
            continue;
        while(top >= 1 && cp(v[st[top-1]], v[st[top]], v[i]) < 0)
            viz[st[top--]] = false;
        st[++top] = i;
        viz[i] = true;
        if(i == v.size() - 1)
            p = -1;
    }
    if(top+1 != v.size())
        return false;
    if(cp(v[st[top-1]], v[st[top]], v[0]) < 0)
        return false;
    vector<Punct> t(st.size());
    for(int i = 0; i < st.size(); ++i)
        t[i] = v[st[i]];
    v = t;
    return true;
}

long long area(const vector<Punct> &v)
{
    Punct O;
    O.x = 0, O.y = 0;
    long long ret = 0;
    for(int i = 0; i < v.size()-1; ++i)
        ret += cp(O, v[i], v[i+1]);
    ret += cp(O, v.back(), v[0]);
    return abs(ret);
}

int main()
{
    ifstream in("gradina.in");
    int n;
    in >> n;
    vector<Punct> v(n);
    string rasp;
    for(int i = 0; i < n; ++i)
    {
        in >> v[i].x >> v[i].y;
        v[i].ind = i;
    }
    in.close();

    long long difMin = (1LL << 62);

    sort(v.begin(), v.end());
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
        {
            if(i == j)
                continue;
            vector<Punct> A, B;

            for(int k = 0; k < n; ++k)
            {
                if(k == i)
                {
                    A.push_back(v[k]);
                    continue;
                }
                if(k == j)
                {
                    B.push_back(v[k]);
                    continue;
                }
                if((cp(v[i], v[j], v[k]) < 0) == (i > j))
                    A.push_back(v[k]);
                else
                    B.push_back(v[k]);
            }
            if(A.size() <= 2 || B.size() <= 2)
                continue;
            if(convex(A) && convex(B))
            {
                long long dif = abs(area(A) - area(B));
                if(dif <= difMin)
                {
                    string s;
                    s.resize(n);
                    for(auto p:A)
                        s[p.ind] = 'V';
                    for(auto p:B)
                        s[p.ind] = 'I';
                    string t = s;
                    for(int i = 0; i < n; ++i)
                        t[i] = (t[i] == 'V' ? 'I' : 'V');
                    if(t < s)
                        s = t;
                    if(dif < difMin)
                        rasp = s, difMin = dif;
                    else if(s < rasp)
                        rasp = s;
                }
            }
        }

    ofstream out("gradina.out");
    out << difMin/2;
    if(difMin % 2 == 0)
        out << ".0";
    else
        out << ".5";
    out << "\n";
    out << rasp;
    out.close();
    return 0;
}