Cod sursa(job #3281126)

Utilizator unomMirel Costel unom Data 28 februarie 2025 14:05:40
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

#define int long long

ifstream in("rubarba.in");
ofstream out("rubarba.out");
int n;
long double ans;
pair<int, int> v[100005];
pair<int, int> s[100005];
pair<long double, long double> w[100005];
int INF = (1LL << 60);

int det(pair<int, int> a, pair<int, int> b, pair<int, int> c)
{
    return (b.first - a.first) * (c.second - a.second) - (c.first - a.first) * (b.second - a.second);
}

int dist(pair<int, int> a, pair<int, int> b)
{
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
    int d = det(v[1], a, b);
    if(d == 0)
    {
        return dist(v[1], a) < dist(v[1], b);
    }

    return d < 0;
}

signed main()
{
    in>>n;

    int poz = 1;
    for(int i = 1; i<=n; i++)
    {
        in>>v[i].first>>v[i].second;

        if(v[i] < v[poz])
        {
            poz = i;
        }
    }

    swap(v[1], v[poz]);
    sort(v + 2, v + n + 1, cmp);

    s[1] = v[1];
    s[2] = v[2];
    int head = 2;

    for(int i = 3; i<=n; i++)
    {
        while(head >= 2 && det(s[head - 1], s[head], v[i]) >= 0)
        {
            head--;
        }

        head++;
        s[head] = v[i];
    }

    s[head + 1] = s[1];
    ans = INF;

    for(int i = 1; i<=head; i++)
    {
        long double unghi = atan2(s[i + 1].second - s[i].second, s[i + 1].first - s[i].first);
        unghi = -unghi;

        long double xmax = -INF;
        long double xmin = INF;
        long double ymax = -INF;
        long double ymin = INF;

        for(int j = 1; j<=head; j++)
        {
            w[j].first = (long double)s[j].first * cos(unghi) - (long double)s[j].second * sin(unghi);
            w[j].second = (long double)s[j].first * sin(unghi) + (long double)s[j].second * cos(unghi);

            xmax = max(xmax, w[j].first);
            xmin = min(xmin, w[j].first);

            ymax = max(ymax, w[j].second);
            ymin = min(ymin, w[j].second);
        }

        long double arie = (long double)(xmax - xmin) * (ymax - ymin);
        ans = min(ans, arie);
    }

    out<<setprecision(2)<<fixed<<ans;

    return 0;
}