Cod sursa(job #2053642)

Utilizator retrogradLucian Bicsi retrograd Data 31 octombrie 2017 23:26:21
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.54 kb
#include <bits/stdc++.h>
 
using namespace std;
 
typedef complex<double> Point;
const double kPi = 4.0 * atan(1.0);
 
const int kMaxN = 100005;
const double kEps = 1e-8;
 
double cross(Point a, Point b) {
    return (conj(a) * b).imag();
}
 
Point rotatePoint(Point p, double ang) {
    return p * polar(1.0, ang);
}
 
struct Caliper {
    Point pivot;
    double angle;
 
    double angleTo(Point oth) {
        double new_ang = arg(oth - pivot);
        return remainder(new_ang - angle, 2.0 * kPi);
    }
    void rotateWith(double ang) {
        angle = remainder(angle + ang, 2.0 * kPi);
    }
 
    double distanceTo(Caliper oth) {
        Point a = rotatePoint(pivot, -angle);
        Point b = rotatePoint(oth.pivot, -angle);
 
        return abs(a.imag() - b.imag());
    }
};
 
template<typename IT>
vector<Point> MakeLowerEnvelope(IT b, IT e) {
    vector<Point> Hull;
    for(auto it = b; it != e; ++it) {
        while(Hull.size() >= 2) {
            Point a = Hull[Hull.size() - 2];
            Point b = Hull[Hull.size() - 1];
 
            if(cross(b - a, (*it) - a) < kEps)
                Hull.pop_back();
            else break;
        }
        Hull.push_back(*it);
    }
    Hull.pop_back();
    return Hull;
}
vector<Point> MakeHull(vector<Point> &Points) {
 
    sort(Points.begin(), Points.end(), [](Point a, Point b) {
        if(a.real() == b.real()) return a.imag() < b.imag();
        return a.real() < b.real();
    });
 
    auto Hull = MakeLowerEnvelope(Points.begin(), Points.end());
    auto Up = MakeLowerEnvelope(Points.rbegin(), Points.rend());
    copy(Up.begin(), Up.end(), back_inserter(Hull));
 
    return Hull;
}
 
int main() {
    freopen("rubarba.in", "r", stdin);
    freopen("rubarba.out", "w", stdout);
    cout << fixed << setprecision(2);
 
    int n;
    cin >> n;
    vector<Point> Points;
    for(int i = 1; i <= n; ++i) {
        int a, b;
        cin >> a >> b;
        Points.emplace_back(a, b);
    }
 
    auto Hull = MakeHull(Points);
 
    if(Hull.size() < 3) {
        cout << 0 << endl;
        return 0;
    }
 
    vector<Caliper> calipers(4);
    vector<int> indices(4, -1);
 
    auto cmpx = [](Point a, Point b) {return a.real() < b.real();};
    auto cmpy = [](Point a, Point b) {return a.imag() < b.imag();};
 
    indices[0] = min_element(Hull.begin(), Hull.end(), cmpy) - Hull.begin();
    indices[1] = max_element(Hull.begin(), Hull.end(), cmpx) - Hull.begin();
    indices[2] = max_element(Hull.begin(), Hull.end(), cmpy) - Hull.begin();
    indices[3] = min_element(Hull.begin(), Hull.end(), cmpx) - Hull.begin();
 
 
    for(int i = 0; i < 4; ++i) {
        calipers[i].angle = i * kPi * 0.5;
        calipers[i].pivot = Hull[indices[i]];
    }
 
    double ans = 1e18;
    double totRot = 0.0;
 
    while(totRot < 2.1 * kPi) {
        double rot = 2.1 * kPi;
        int choose = -1;
 
        double area = calipers[0].distanceTo(calipers[2]) * calipers[1].distanceTo(calipers[3]);
        ans = min(ans, area);
 
        for(int i = 0; i < 4; ++i) {
            double ind = indices[i];
            double dang = calipers[i]
                .angleTo(Hull[(indices[i] + 1) % Hull.size()]);
 
            if(rot > dang) {
                rot = dang;
                choose = i;
            }
        }
 
        for(int i = 0; i < 4; ++i) 
            calipers[i].rotateWith(rot);
        indices[choose] = (indices[choose] + 1) % Hull.size();
        assert(calipers[choose].angleTo(Hull[indices[choose]]) < kEps);
        calipers[choose].pivot = Hull[indices[choose]];
 
        totRot += rot;
    }
 
    cout << ans << endl;
 
    return 0;
}