Cod sursa(job #2051685)

Utilizator teoionescuIonescu Teodor teoionescu Data 29 octombrie 2017 13:42:05
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.19 kb
#include <bits/stdc++.h>
using namespace std;
 
const double pi = 4.*atan(1);
const double eps = 1e-12;
 
struct point {
    double x, y;
};
struct line {
    double a, b;
};
typedef complex<double> comp;
 
double ccw(point a, point b, point c) {
    return a.x*b.y - a.y*b.x + b.x*c.y - b.y*c.x + c.x*a.y - c.y*a.x;
}
 
double dist(point a, point b) {
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
 
int eq(double d1,double d2) {
    return abs(d1-d2) < eps;
}

void halt() {
    while(1);
}
 
line fromPoints(point p1, point p2) {
    if(eq(p1.x, p2.x)) halt();
    double a = (p1.y - p2.y) / (p1.x - p2.x);
    return {a, p1.y - a*p1.x};
}
 
point inters(line l1, line l2) {
    if(eq(l1.a, l2.a)) halt();
    double x = (l2.b - l1.b) / (l1.a - l2.a);
    return {x, l1.a*x + l1.b};
}
 
line perpend(line l, point gp) {
    if(eq(l.a, 0.)) halt();
    return {double(-1)/l.a, gp.y + gp.x/l.a};
}
 
point proiect(point p, line l) {
    return inters(l, perpend(l, p));
}
 
void rotate(vector<double> &xr, vector<double> &yr) {
    double t = 2*pi/1e10;
    comp w = {cos(t), sin(t)};
    for(int i=0; i<(int)xr.size(); i++) {
        comp cr = w * (comp){xr[i], yr[i]};
        xr[i]=real(cr);
        yr[i]=imag(cr);
    }
}
 
vector<int> chull(vector<double> &xr, vector<double> &yr) {
    int n = xr.size();
    vector<int> v(n);
    for(int i=0; i<n; i++) v[i] = i;
    sort(v.begin(), v.end(), [&xr, &yr](const int &i, const int &j) {
        if(eq(xr[i], xr[j])) {
            return yr[i] < yr[j];
        }
        return xr[i] < xr[j];
    });
    int i1 = v[0];
    swap(v[0], v[n-1]);
    v.pop_back();
    sort(v.begin(), v.end(), [i1, &xr, &yr](const int &i, const int &j) {
        return ccw((point){xr[i1], yr[i1]}, (point){xr[i],yr[i]}, (point){xr[j], yr[j]}) > 0.;
    });
    vector<int> cs;
    cs.push_back(i1);
    for(auto it : v) {
        while(cs.size() >= 2 && 
            ccw(
                (point){xr[cs[cs.size()-2]], yr[cs[cs.size()-2]]},
                (point){xr[cs[cs.size()-1]],yr[cs[cs.size()-1]]}, 
                (point){xr[it], yr[it]}) < 0.) {
            cs.pop_back();
        }
        cs.push_back(it);
    }
    return cs;
}
 
int cb(int st, int dr, function<double(int)> const& f) {
    int i = st, pas=1<<18;
    while(pas) {
        if(i+pas<dr && f(i+pas) < f(i+pas+1)) i+=pas;
        pas>>=1;
    }
    if(f(i+pas) < f(i+pas+1)) {
        return i+1;
    }
    return i;
}
 
int main() {
    freopen("rubarba.in", "r", stdin);
    freopen("rubarba.out", "w", stdout);
    vector<double> xr, yr;
    int n;
     
    cin>>n;
    xr.resize(n);
    yr.resize(n);
    for(int i=0; i<n; i++) {
        cin>>xr[i]>>yr[i];
    }
    rotate(xr, yr);
    vector<int> hulls = chull(xr, yr);
    int hn = (int)hulls.size();
    for(int i=0; i<hn; i++) {
        hulls.push_back(hulls[i]);
    }
    double ans = n < 3 ? 0. : 1e100;
    for(int i=0; i<hn; i++) {
        point p1 = (point){xr[hulls[i]], yr[hulls[i]]};
        point p2 = (point){xr[hulls[i+1]], yr[hulls[i+1]]};
        line l = fromPoints(p1, p2);
        int w = cb(i+1, i+hn, [&xr, &yr, &l, &hulls](const int &i) -> double {
            point p = {xr[hulls[i]], yr[hulls[i]]};
            return dist(p, proiect(p, l));
        });
        point pw = {xr[hulls[w]], yr[hulls[w]]};
        int drw = cb(i+1, w, [&xr, &yr, &l, &hulls, &pw](const int &i) -> double {
            point p = {xr[hulls[i]], yr[hulls[i]]};
            return dist(proiect(pw, l), proiect(p, l));
        });
        int stw = cb(w, i+hn, [&xr, &yr, &l, &hulls, &pw](const int &i) -> double {
            point p = {xr[hulls[i]], yr[hulls[i]]};
            return dist(proiect(pw, l), proiect(p, l));
        });
        point pstw = {xr[hulls[stw]], yr[hulls[stw]]};
        double stwidth = dist(proiect(pw, l), proiect(pstw, l));
 
        point pdrw = {xr[hulls[drw]], yr[hulls[drw]]};
        double drwidth = dist(proiect(pw, l), proiect(pdrw, l));
 
        double height = dist(pw, proiect(pw, l));
        ans = min(ans, (stwidth + drwidth) * height);
    }
    cout.precision(2);
    cout<<fixed<<ans<<'\n';
    return 0;
}