Cod sursa(job #2832835)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 14 ianuarie 2022 13:36:15
Problema Rubarba Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("rubarba.in");
ofstream fout("rubarba.out");

using ld = long double;
const int NMAX(100005);
struct chestie
{
    int x, y;
} v[NMAX], st[NMAX];

ld pi = 4 * atan(1);
ld det(chestie a, chestie b, chestie c)
{
    return a.x * b.y + a.y * c.x + b.x * c.y - c.x * b.y - a.y * b.x - a.x * c.y;
}
inline bool cmp1(chestie a, chestie b)
{
    if(a.y == b.y)
        return a.x > b.x;
    return a.y < b.y;
}
inline bool cmp2(chestie a, chestie b)
{
    return (det(v[1], a, b) > 0.0);
}

pair<ld, ld> convP(ld x, ld y, ld angle, chestie p)
{
    ld s = sin(-angle);
    ld c = cos(-angle);
    ld ax = p.x - x;
    ld ay = p.y - y;
    ld newX = ax * c - ay * s + x;
    ld newY = ax * s + ay * c + y;
    return {newX, newY};
}

int main()
{
    int n;
    fin >> n;

    for(int i = 1; i <= n; ++i)
        fin >> v[i].x >> v[i].y;

    sort(v + 1, v + n + 1, cmp1);
    sort(v + 2, v + n + 1, cmp2);

    int nr = 2;
    st[1] = v[1];
    st[2] = v[2];
    v[n + 1] = v[1];
    for(int i = 3; i <= n + 1; ++i)
    {
        while(nr > 1 && det(st[nr - 1], st[nr], v[i]) <= 0.0)
            --nr;
        st[++nr] = v[i];
    }
    ld minn = 1e9;
    ///obs: latura paralela cu una de pe infasuratoare
    for(int i = 1; i < nr; ++i)
    {
        chestie a = st[i], b = st[i + 1];
        if(a.y > b.y)
            swap(a, b);
        b.x -= a.x;
        b.y -= a.y;
        ld ang = atan2(b.y, b.x);

        ld minnX = 1e9, minnY = 1e9, maxxX = -1e9, maxxY = -1e9;
        for(int j = 1; j <= nr; ++j)
        {
            pair<ld, ld> newP = convP(a.x, a.y, ang, st[j]);
            if(st[j].x == a.x && st[j].y == a.y)
                newP = {a.x, a.y};
            minnX = min(minnX, newP.first), maxxX = max(maxxX, newP.first);
            minnY = min(minnY, newP.second), maxxY = max(maxxY, newP.second);
        }
        minn = min(minn, abs((maxxX - minnX) * (maxxY - minnY)));
    }

    fout << fixed << setprecision(3) << minn << '\n';
    return 0;
}