Cod sursa(job #2975302)

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

#pragma GCC optimize ("O1")
#pragma GCC optimize ("O2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

using namespace std;

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

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

#define ll long long

struct pdd {
    double first, second;
};

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

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

bool cmp1 (pdd x, pdd y)
{
    return orientare(mult1[1], x, y) < 0;
}

bool cmp2 (pdd x, pdd y)
{
    return orientare(mult2[1], x, y) < 0;
}

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.push_back('I');
        }
        else
        {
            mult2[++pct2] = v[i];
            curr.push_back('V');
        }
    }
    if (pct1 < 3 || pct2 < 3)
    {
        return false;
    }
    chhhh.clear();
    sort(mult1 + 1, mult1 + pct1 + 1, cmp1);
    chhhh.push_back(mult1[1]);
    chhhh.push_back(mult1[2]);
    for (int i = 3; i <= pct1; i++)
    {
        while (chhhh.size() > 1 && orientare(chhhh[chhhh.size() - 2], chhhh[chhhh.size() - 1], mult1[i]) >= 0)
        {
            return false;
        }
        chhhh.push_back(mult1[i]);
    }
    chhhh.clear();
    sort(mult2 + 1, mult2 + pct2 + 1, cmp2);
    chhhh.push_back(mult2[1]);
    chhhh.push_back(mult2[2]);
    for (int i = 3; i <= pct2; i++)
    {
        while (chhhh.size() > 1 && orientare(chhhh[chhhh.size() - 2], chhhh[chhhh.size() - 1], mult2[i]) >= 0)
        {
            return false;
        }
        chhhh.push_back(mult2[i]);
    }
    return true;
}

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

double arie2 ()
{
    double ans = 0;
    for (int i = 3; i <= pct2; i++)
    {
        ans += orientare(mult2[1], mult2[i - 1], mult2[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;
    }
    out << fixed << setprecision(1);
    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();
                double anou = abs(a1 - a2);
                if (abs(anou - ans) < eps && curr < minimuuu)
                {
                    ans = anou;
                    minimuuu = curr;
                }
                else
                {
                    if (anou < ans)
                    {
                        ans = anou;
                        minimuuu = curr;
                    }
                }
                //cout << ans << " " << minimuuu << '\n';
            }
        }
    }
    out << ans << '\n' << minimuuu;
    in.close();
    out.close();
    return 0;
}