Cod sursa(job #2959319)

Utilizator OvidRata Ovidiu Ovid Data 30 decembrie 2022 17:35:32
Problema Rubarba Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.28 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


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);
    });
    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=(-1.0000/a)*ptt.x+p.y+(1.0000/a)*p.x;
    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)/(sign(p2.x-p1.x)*max(abs(p2.x-p1.x), 1e-18)),
            p2.y-((p2.y-p1.y)/(sign(p2.x-p1.x)*max(abs(p2.x-p1.x), 1e-18)))*p2.x
            );
}


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++){
        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]) )  ) );
    }
    cout<<fixed<<setprecision(2)<<res;
    return 0;
}