Cod sursa(job #2870813)

Utilizator domistnSatnoianu Dominic Ioan domistn Data 12 martie 2022 16:27:44
Problema Rubarba Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cmath>

#define NMAX 100005
#define EPS 1e-9

using namespace std;

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

typedef long double ld;

struct pct {
    ld x, y;
} a[NMAX];

int n;

inline ld vabs(const ld X) {
    return X > 0 ? X : -X;
}

inline bool isEqual(const ld X, const ld Y) {
    return vabs(X - Y) <= EPS;
}

inline ld calcArea(const ld ang) {
    ld minx = 1e18, maxx = -1e18, miny = 1e18, maxy = -1e18;
    const ld sn = sin(ang), cs = cos(ang);
    for(int i = 1; i <= n; ++i) {
        const pct rotated = {a[i].x * cs - a[i].y * sn,
                             a[i].x * sn + a[i].y * cs};
        minx = min(minx, rotated.x);
        maxx = max(maxx, rotated.x);
        miny = min(miny, rotated.y);
        maxy = max(maxy, rotated.y);
    }
    return (maxx - minx) * (maxy - miny);
}

ld cbMaxArea() {
    ld st = 0, dr = M_PI / 2, mij;
    while(!isEqual(st, dr)) {
        mij = (st + dr) / 2;
        if(calcArea(mij) < calcArea(mij + EPS))
            dr = mij;
        else st = mij;
    }
    return calcArea(st);
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> a[i].x >> a[i].y;
    fout << fixed << setprecision(7) << cbMaxArea();
    return 0;
}