Cod sursa(job #2417292)

Utilizator Carol_LucaCarol Luca Carol_Luca Data 29 aprilie 2019 14:31:07
Problema Gradina Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.7 kb
/// gradina



#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;

}