Cod sursa(job #2333723)

Utilizator DavidLDavid Lauran DavidL Data 1 februarie 2019 21:15:16
Problema Gradina Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.48 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fi("gradina.in");
ofstream fo("gradina.out");

const int NMAX = 300;

struct punct
{
    int x, y;
};

bool operator <(const punct &a, const punct &b)
{
    if (a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

punct P[NMAX];
punct sus[NMAX], jos[NMAX];
int cntSus, cntJos;
int n;
punct stivaSus[NMAX], stivaJos[NMAX];
int kSus, kJos;
bool afara;

int verifica(punct A, punct B, punct C)
{
    return A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y) ;
}

long double dist(punct A, punct B)
{
    return (long double)sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

long double unghi(punct A, punct B)
{
    if (A.x <= B.x && A.y <= B.y) // cadranul 1
    {
        return 2 + 1.00 * (B.y - A.y) / dist(A, B);
    }
    else if (A.x >= B.x && A.y <= B.y) // cadranul 2
    {
        return 3 + 1.00 * (A.x - B.x) / dist(A, B);
    }
    else if (A.x >= B.x && A.y >= B.y) // cadranul 3
    {
        return 1.00 * (A.y - B.y) / dist(A, B);
    }
    else // cadranul 4
    {
        return 1 + 1.00 * (B.x - A.x) / dist(A, B);
    }
}

long double faTot(punct A[NMAX], int n) // returneaza aria
{
    kJos = 0;
    kSus = 0;

    int dr = unghi(A[1], A[n]);
    stivaSus[++kSus] = A[1];
    stivaJos[++kJos] = A[1];

    for (int i = 2; i <= n; i++)
    {
        if (unghi(A[1], A[i]) > dr || i == n) // sus
        {
            while (kSus >= 2 && unghi(stivaSus[kSus - 1], stivaSus[kSus]) < unghi(stivaSus[kSus - 1], A[i]))
                kSus--, afara = 1;
            stivaSus[++kSus] = A[i];
        }
        if (unghi(A[1], A[i]) < dr || i == n) // jos
        {
            while (kJos >= 2 && unghi(stivaJos[kJos - 1], stivaJos[kJos]) > unghi(stivaJos[kJos - 1], A[i]))
                kJos--, afara = 1;
            stivaJos[++kJos] = A[i];
        }
    }
    vector <punct> poligon;
    for (int i = 1; i <= kSus; i++)
        poligon.push_back(stivaSus[i]);
    for (int i = kJos - 1; i >= 1; i--)
        poligon.push_back(stivaJos[i]);

    long double ret = 0;
    for (int i = 1; i < poligon.size(); i++)
    {
        ret += (poligon[i - 1].x * poligon[i].y - poligon[i].x * poligon[i - 1].y);
    }
    ret = ret / 2.00;
    return abs(ret);
}

int main()
{
    fi >> n;
    for (int i = 1; i <= n; i++)
        fi >> P[i].x >> P[i].y;

    long double minim = 2000000000;
    string configOptim;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
                continue;

            // i la ion, j la domnu vasile
            punct baza, varf; // baza=punctul care e mai in stanga
            if (P[j] < P[i])
                baza = P[j], varf = P[i];
            else
                baza = P[i], varf = P[j];

            cntSus = cntJos = 0;
            // sus punem J, jos punem I
            string config = "";
            config.resize(n);
            sus[++cntSus] = P[j];
            jos[++cntJos] = P[i];
            config[i - 1] = 'I';
            config[j - 1] = 'V';

            for (int k = 1; k <= n; k++)
            {
                if (i == k || j == k)
                    continue;

                if (verifica(baza, varf, P[k]) > 0) // e sus, la Vasile
                {
                    sus[++cntSus] = P[k];
                    config[k - 1] = 'V';
                }
                else
                {
                    jos[++cntJos] = P[k];
                    config[k - 1] = 'I';
                }
            }
            sort(sus + 1, sus + cntSus + 1);
            sort(jos + 1, jos + cntJos + 1);

            afara = 0;
            long double a1 = faTot(sus, cntSus);
            if (afara)
                continue;
            afara = 0;
            long double a2 = faTot(jos, cntJos);
            if (afara)
                continue;

            //for (int i = 1; i <= cntJos; i++)
                //cout << jos[i].x << ", " << jos[i].y << "\n";

            string opus = "";
            for (auto x: config)
                opus += (x == 'I' ? 'V' : 'I');

            if (abs(a2 - a1) < minim || abs(a2 - a1) == minim && (config < configOptim || opus < configOptim))
            {
                minim = abs(a2 - a1);
                configOptim = min(config, opus);
            }
        }
    }
    fo << fixed << setprecision(1) << minim << "\n" << configOptim;

    return 0;
}