Cod sursa(job #2975298)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 6 februarie 2023 09:21:43
Problema Gradina Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.18 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>

using namespace std;

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

const double eps = 1e-3;
const int max_size = 251;

#define pdd pair <double, double>

pdd mult1[max_size], mult2[max_size], ch1[max_size], ch2[max_size], v[max_size];
vector <pdd> jos, sus;
int n, pct1, pct2, rez1, rez2;
string curr;

double orientare (pdd x, pdd y, pdd z)
{
    return (double)((int64_t)x.first * (y.second - z.second) + (int64_t)y.first * (z.second - x.second) + (int64_t)z.first * (x.second - y.second));
}

bool ch (int x, int y)
{
    curr.clear();
    pct1 = 0;
    pct2 = 0;
    for (int i = 1; i <= n; i++)
    {
        if (orientare(v[x], v[y], v[i]) < 0)
        {
            mult1[++pct1] = v[i];
            curr += 'I';
        }
        else
        {
            mult2[++pct2] = v[i];
            curr += 'V';
        }
    }
    if (pct1 < 3 || pct2 < 3)
    {
        return false;
    }
    sus.clear();
    jos.clear();
    sort(mult1 + 1, mult1 + pct1 + 1);
    sus.push_back(mult1[1]);
    jos.push_back(mult1[1]);
    for (int i = 2; i <= pct1; i++)
    {
        while (sus.size() > 1 && orientare(sus[sus.size() - 2], sus[sus.size() - 1], mult1[i]) >= 0)
        {
            sus.pop_back();
        }
        while (jos.size() > 1 && orientare(jos[jos.size() - 2], jos[jos.size() - 1], mult1[i]) <= 0)
        {
            jos.pop_back();
        }
        sus.push_back(mult1[i]);
        jos.push_back(mult1[i]);
    }
    sus.pop_back();
    reverse(sus.begin(), sus.end());
    sus.pop_back();
    rez1 = 0;
    for (auto f : jos)
    {
        ch1[++rez1] = f;
    }
    for (auto f : sus)
    {
        ch1[++rez1] = f;
    }
    if (rez1 != pct1)
    {
        return false;
    }
    sus.clear();
    jos.clear();
    sort(mult2 + 1, mult2 + pct2 + 1);
    sus.push_back(mult2[1]);
    jos.push_back(mult2[1]);
    for (int i = 2; i <= pct2; i++)
    {
        if (sus.size() > 1 && orientare(sus[sus.size() - 2], sus[sus.size() - 1], mult2[i]) >= 0)
        {
            sus.pop_back();
        }
        if (jos.size() > 1 && orientare(jos[jos.size() - 2], jos[jos.size() - 1], mult2[i]) <= 0)
        {
            jos.pop_back();
        }
        sus.push_back(mult2[i]);
        jos.push_back(mult2[i]);
    }
    sus.pop_back();
    reverse(sus.begin(), sus.end());
    sus.pop_back();
    rez2 = 0;
    for (auto f : jos)
    {
        ch2[++rez2] = f;
    }
    for (auto f : sus)
    {
        ch2[++rez2] = f;
    }
    if (rez2 != pct2)
    {
        return false;
    }
    return true;
}

double arie1 ()
{
    double ans = 0;
    for (int i = 3; i <= pct1; i++)
    {
        ans += orientare(ch1[1], ch1[i - 1], ch1[i]) / 2;
    }
    return ans;
}

double arie2 ()
{
    double ans = 0;
    for (int i = 3; i <= pct2; i++)
    {
        ans += orientare(ch2[1], ch2[i - 1], ch2[i]) / 2;
    }
    return ans;
}

int main ()
{
    string minimuuu = "X";
    double ans = 1e9 + 1;
    in >> n;
    for (int i = 1; i <= n; i++)
    {
        in >> v[i].first >> v[i].second;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
            {
                continue;
            }
            if (ch(i, j))
            {
                double a1 = arie1(), a2 = arie2();
                //cout << a1 << " " << a2 << " " << curr << '\n';
                if (abs(abs(a1 - a2) - ans) < eps && curr < minimuuu)
                {
                    ans = abs(a1 - a2);
                    minimuuu = curr;
                }
                else
                {
                    if (abs(a1 - a2) < ans)
                    {
                        ans = abs(a1 - a2);
                        minimuuu = curr;
                    }
                }
                //cout << ans << " " << minimuuu << '\n';
            }
        }
    }
    out << fixed << setprecision(1);
    out << ans << '\n' << minimuuu;
    in.close();
    out.close();
    return 0;
}