Cod sursa(job #2959336)

Utilizator OvidRata Ovidiu Ovid Data 30 decembrie 2022 18:07:46
Problema Rubarba Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.8 kb
#include<bits/stdc++.h>
using namespace std;

string numeFisier="rubarba";
ifstream fin(numeFisier+".in"); ofstream fout(numeFisier+".out");
#define cin fin
#define cout fout

#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll
#define double long double

int t, n;
struct pt {
    double x, y;
};

pt pts[100010];

int orientation(pt a, pt b, pt c) {
    double v = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
    if (v < 0) return -1; // clockwise
    if (v > 0) return +1; // counter-clockwise
    return 0;
}

bool cw(pt a, pt b, pt c, bool include_collinear) {
    int o = orientation(a, b, c);
    return o < 0 || (include_collinear && o == 0);
}
bool ccw(pt a, pt b, pt c, bool include_collinear) {
    int o = orientation(a, b, c);
    return o > 0 || (include_collinear && o == 0);
}

void convex_hull(vector<pt>& a, bool include_collinear = false) {
    if (a.size() == 1)
        return;

    sort(a.begin(), a.end(), [](pt a, pt b) {
        return make_pair(a.x, a.y) < make_pair(b.x, b.y);
    });
    a.erase(unique(a.begin(), a.end(), [](pt a, pt b){return a.x==b.x && a.y==b.y;} ), a.end());
    pt p1 = a[0], p2 = a.back();
    vector<pt> up, down;
    up.push_back(p1);
    down.push_back(p1);
    for (int i = 1; i < (int)a.size(); i++) {
        if (i == a.size() - 1 || cw(p1, a[i], p2, include_collinear)) {
            while (up.size() >= 2 && !cw(up[up.size()-2], up[up.size()-1], a[i], include_collinear))
                up.pop_back();
            up.push_back(a[i]);
        }
        if (i == a.size() - 1 || ccw(p1, a[i], p2, include_collinear)) {
            while (down.size() >= 2 && !ccw(down[down.size()-2], down[down.size()-1], a[i], include_collinear))
                down.pop_back();
            down.push_back(a[i]);
        }
    }

    if (include_collinear && up.size() == a.size()) {
        reverse(a.begin(), a.end());
        return;
    }
    a.clear();
    for (int i = 0; i < (int)up.size(); i++)
        a.push_back(up[i]);
    for (int i = down.size() - 2; i > 0; i--)
        a.push_back(down[i]);
    reverse(a.begin(), a.end());
}


pt projection(double a, double b, pt p){
    pt ptt;
    ptt.x=(a*p.y+p.x-a*b)/(a*a+1);
    ptt.y=a*ptt.x+b;
    return ( ptt );
}
double sign(double x){
    if( x>=0 ){
        return 1;
    }
    return x/abs(x);
}
double dist(pt p1, pt p2){
    return sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) );
}
pair<double, double> eq(pt p1, pt p2){
    return mp(
            (p2.y-p1.y)/(p2.x-p1.x ),
            p2.y-(p2.y-p1.y)/(p2.x-p1.x)*p2.x
            );
}

pt projection_vert(double b, pt p){
    pt pp; pp.x=b; pp.y=p.y;
    return pp;
}

int32_t main(){
    INIT
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>pts[i].x>>pts[i].y;
    }

    vector<pt> vec={};
    for(int i=1; i<=n; i++){
        vec.pb(pts[i]);
    }
    convex_hull(vec, false);

    if(vec.size()<=2){
        cout<<fixed<<setprecision(2)<<((double)0);
        return 0;
    }

    int h=1, i1=1, i2=2;
    double res=1e18;
    int n = vec.size();
    for(int i=0; i<vec.size(); i++){
        if( abs(vec[i].x-vec[(i+1)%n].x)>(0.5) ) {
            auto pr = eq(vec[i], vec[(i + 1) % n]);
            double a = pr.ft, b = pr.sc;
            double dsty = dist(vec[h], projection(a, b, vec[h]));
            double span = dist(projection(a, b, vec[i1]), projection(a, b, vec[i2]));
            while ((dist(vec[(h + 1) % n], projection(a, b, vec[(h + 1) % n]))) > dsty) {
                dsty = (dist(vec[(h + 1) % n], projection(a, b, vec[(h + 1) % n])));
                h++;
                h %= n;
            }
            while (true) {
                int nxt1 = (i1 + 1) % n, nxt2 = (i2 + 1) % n;
                if (dist(projection(a, b, vec[nxt2]), projection(a, b, vec[i1])) >
                    dist(projection(a, b, vec[i2]), projection(a, b, vec[i1]))) {
                    i2++;
                    i2 %= n;
                    continue;
                }
                if (dist(projection(a, b, vec[i2]), projection(a, b, vec[nxt1])) >
                    dist(projection(a, b, vec[i2]), projection(a, b, vec[i1]))) {
                    i1++;
                    i1 %= n;
                    continue;
                }
                break;
            }
            res = min(res, dsty * (dist(projection(a, b, vec[i1]), projection(a, b, vec[i2]))));
        }
        else{
            double b=vec[i].x;
            double dsty = dist(vec[h], projection_vert(b, vec[h]));
            double span = dist(projection_vert(b, vec[i1]), projection_vert(b, vec[i2]));
            while ((dist(vec[(h + 1) % n], projection_vert(b, vec[(h + 1) % n]))) > dsty) {
                dsty = (dist(vec[(h + 1) % n], projection_vert(b, vec[(h + 1) % n])));
                h++;
                h %= n;
            }
            while (true) {
                int nxt1 = (i1 + 1) % n, nxt2 = (i2 + 1) % n;
                if (dist(projection_vert(b, vec[nxt2]), projection_vert( b, vec[i1])) >
                    dist(projection_vert( b, vec[i2]), projection_vert(b, vec[i1]))) {
                    i2++;
                    i2 %= n;
                    continue;
                }
                if (dist(projection_vert(b, vec[i2]), projection_vert( b, vec[nxt1])) >
                    dist(projection_vert( b, vec[i2]), projection_vert( b, vec[i1]))) {
                    i1++;
                    i1 %= n;
                    continue;
                }
                break;
            }
            res = min(res, dsty * (dist(projection_vert( b, vec[i1]), projection_vert( b, vec[i2]))));
        }
    }
    cout<<fixed<<setprecision(2)<<res;
    return 0;
}