Cod sursa(job #2949479)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 30 noiembrie 2022 19:00:04
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.34 kb
//
// Created by mihai145 on 30.11.2022.
//

// #include <iostream>
#include <complex>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

#include <fstream>
ifstream cin("rubarba.in");
ofstream cout("rubarba.out");

#define x() real()
#define y() imag()

using Point = complex<double>;
using Poly = vector<Point>;
const double kPi = 4.0 * atan(1.0);

double cross(Point a, Point b) { return (conj(a) * b).y(); }
double det(Point a, Point b, Point c) { return cross(b - a, c - a); }
Point rotateCCW(Point a, double theta) { return a * polar(1.0, theta); }

pair<Poly, Poly> ConvexHull(Poly P) {
    sort(P.begin(), P.end(), [](Point &a, Point &b) {
        return make_pair(a.x(), a.y()) < make_pair(b.x(), b.y());
    });
    P.erase(unique(P.begin(), P.end()), P.end());

    Poly up, dw;
    for (auto &p : P) {
        while (up.size() >= 2 && det(up[up.size() - 2], up.back(), p) > 0) { up.pop_back(); }
        up.push_back(p);

        while (dw.size() >= 2 && det(dw[dw.size() - 2], dw.back(), p) < 0) { dw.pop_back(); }
        dw.push_back(p);
    }

    return {up, dw};
}

struct Caliper {
    Point pivot; double angle;
    double AngleTo(Point oth) {
        double new_ang = arg(oth - pivot);
        double res = remainder(new_ang - angle, 2.0 * kPi);
        if (res < 0) { res += 2. * kPi; }
        return res;
    }
    void RotateCCW(double ang) { angle = remainder(angle + ang, 2.0 * kPi); }
    void ChangePivot(Point oth) { pivot = oth; }
    double DistanceTo(Caliper oth) {    // Need to have same angle
        Point a = rotateCCW(pivot, -angle), b = rotateCCW(oth.pivot, -angle);
        return abs(a.imag() - b.imag());
    }
};

int n;
void test() {
    Poly p;
    for (int i = 0; i < n; i++) {
        int x, y; cin >> x >> y;
        p.emplace_back(1. * x, 1. * y);
    }

    pair<Poly, Poly> h = ConvexHull(p);
    Poly hull = h.second;
    for (int i = (int)h.first.size() - 2; i > 0; i--) { hull.push_back(h.first[i]); }

    vector<Caliper> calipers(4);
    vector<int> indices(4, 0);

    for (int i = 1; i < (int)hull.size(); i++) {
        if (hull[i].imag() < hull[indices[0]].imag()) { indices[0] = i; } // bottom || OX
        if (hull[i].real() > hull[indices[1]].real()) { indices[1] = i; } // right || OY
        if (hull[i].imag() > hull[indices[2]].imag()) { indices[2] = i; } // top || OX
        if (hull[i].real() < hull[indices[3]].real()) { indices[3] = i; } // left || OY
    }

    for (int i = 0; i < 4; i++) {
        calipers[i].pivot = hull[indices[i]];
        calipers[i].angle = 0.5 * i * kPi;
    }

    double total = 0., min_area = 1e15;
    while (total <= 2. * kPi) {
        min_area = min(min_area, (calipers[0].DistanceTo(calipers[2]) * calipers[1].DistanceTo(calipers[3])));

        double rot = 2. * kPi;
        int choose = -1;
        for (int i = 0; i < 4; i++) {
            double ang = calipers[i].AngleTo(hull[(indices[i] + 1) % hull.size()]);
            if (ang < rot) {
                rot = ang;
                choose = i;
            }
        }

        total += rot;
        for (int i = 0; i < 4; i++) { calipers[i].RotateCCW(rot); }

        indices[choose] = (indices[choose] + 1) % hull.size();
        calipers[choose].pivot = hull[indices[choose]];
    }

    cout << fixed << setprecision(2) << min_area << '\n';
}

int main() {
    while (cin >> n) { test(); }
    return 0;
}