Cod sursa(job #2611086)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 6 mai 2020 12:56:17
Problema Gradina Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.84 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("gradina.in");
ofstream g("gradina.out");

typedef pair < int, int > PII;
typedef pair < PII, int > PIII;

using ld = long double;
typedef pair < string, ld > Answer;

const int NMAX = 255;
const long long INF = 1LL * 1e18;
const ld eps = 1e-10, HALF = 0.5000000000, ONE = 1.0000000000;

int N;
PIII A[NMAX];

char S[NMAX];

static inline void Read ()
{
    f.tie(nullptr);

    f >> N;

    for(int i = 1; i <= N; ++i)
        f >> A[i].first.first >> A[i].first.second, A[i].second = i;

    return;
}

static inline ld Frac (ld a, ld b)
{
    return (ld)(a / b) * ONE;
}

int Stiva[NMAX], K;
bool Sel[NMAX];

static inline long long Det2 (PII A, PII B)
{
    return (1LL * A.first * B.second - 1LL * A.second * B.first);
}

static inline long long Det3 (PII A, PII B, PII 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);
}

static inline ld my_abs (ld X)
{
    if(X < eps)
        return -X;

    return X;
}

static inline pair < bool, ld > ConvexHull (vector < int > Set, char Fill)
{
    for(auto it : Set)
        S[A[it].second] = Fill;

    for(int i = 1; i <= N; ++i)
        Sel[i] = 0;

    K = 0;

    ///
    Stiva[++K] = Set[0];

    Stiva[++K] = Set[1];
    Sel[Set[1]] = 1;

    for(int i = 2; i < (int)Set.size(); ++i)
    {
        while(K > 1 && Det3(A[Set[i]].first, A[Stiva[K - 1]].first, A[Stiva[K]].first) > 0)
        {
            Sel[Stiva[K]] = 0;

            --K;
        }

        Stiva[++K] = Set[i];
        Sel[Set[i]] = 1;
    }

    for(int i = (int)Set.size() - 1; i >= 0; --i)
        if(!Sel[Set[i]])
        {
            while(K > 1 && Det3(A[Set[i]].first, A[Stiva[K - 1]].first, A[Stiva[K]].first) > 0)
            {
                Sel[Stiva[K]] = 0;

                --K;
            }

            Stiva[++K] = Set[i];
            Sel[Set[i]] = 1;
        }

    if(Stiva[K] != Stiva[1])
        return {0, 0};
    ///

    int r = 0;
    for(int i = 1; i <= N; ++i)
        r += Sel[i];

    if(r != (int)Set.size())
        return {0, 0};

    ld Area = 0;

    for(int i = 1; i < K; ++i)
        Area += Det2(A[Stiva[i]].first, A[Stiva[i + 1]].first);

    Area = my_abs(Area);
    Area *= HALF;

    return {1, Area};
}

static inline Answer GetSol (int Ind1, int Ind2)
{
    Answer r;
    r.second = INF;

    vector < int > Set_1, Set_2;

    for(int i = 1; i <= N; ++i)
    {
        if(i == Ind1)
        {
            Set_1.push_back(i);

            continue;
        }

        if(i == Ind2)
        {
            Set_2.push_back(i);

            continue;
        }

        if(A[Ind1].first.first == A[Ind2].first.first)
        {
            if(A[i].first.first <= A[Ind1].first.first)
                Set_1.push_back(i);
            else
                Set_2.push_back(i);

            continue;
        }

        if(A[Ind1].first.second == A[Ind2].first.second)
        {
            if(A[i].first.second <= A[Ind1].first.second)
                Set_1.push_back(i);
            else
                Set_2.push_back(i);

            continue;
        }

        ld m = Frac(A[Ind1].first.second - A[Ind2].first.second, A[Ind1].first.first - A[Ind2].first.first);
        ld b = (ld)(A[Ind1].first.second) - m * (ld)(A[Ind1].first.first);

        ld Height_Line = (ld)(A[i].first.first) * m + b;

        if((ld)A[i].first.second - Height_Line < eps)
            Set_1.push_back(i);
        else
            Set_2.push_back(i);
    }

    if((int)Set_1.size() < 3 || (int)Set_2.size() < 3)
        return r;

    pair < bool, ld > P_1 = ConvexHull(Set_1, 'I');
    pair < bool, ld > P_2 = ConvexHull(Set_2, 'V');

    if(!P_1.first || !P_2.first)
        return r;

    r.second = my_abs(P_1.second - P_2.second);

    if(S[1] == 'V')
    {
        for(int i = 1; i <= N; ++i)
            if(S[i] == 'V')
                S[i] = 'I';
            else
                S[i] = 'V';
    }

    for(int i = 1; i <= N; ++i)
        r.first.push_back(S[i]);

    return r;
}

static inline void Solve ()
{
    sort(A + 1, A + N + 1);

    Answer ans;
    ans.second = INF;

    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            if(i != j)
            {
                Answer Now = GetSol(i, j);

                if(Now.second < ans.second)
                    ans = Now;
                else if(Now.second == ans.second && Now.first < ans.first)
                    ans = Now;
            }

    g << setprecision(1) << fixed << (ld)ans.second << '\n' << ans.first << '\n';

    return;
}

int main()
{
    Read();

    Solve();

    return 0;
}