Cod sursa(job #3359063)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 23 iunie 2026 16:09:36
Problema Rubarba Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.99 kb
#include <fstream>

#include <utility>
#define x first
#define y second

#include <algorithm>

#include <iomanip>

#include <cstdint>
#include <cmath>

using namespace std;

ifstream in("rubarba.in");
ofstream out("rubarba.out");

typedef pair <int, int> pii;
typedef pair <double, double> pdd;
const int nmax = 1e5;
///const double epsilon = 1e-15;
int n; pii a[nmax + 2];

int64_t crossproduct(pii a0, pii a1, pii a2){
    return 1ll * (a1.x - a0.x) * (a2.y - a0.y) - 1ll * (a2.x - a0.x) * (a1.y - a0.y);
}

/// ---> convex hull to get relevant points <--- ///
pii stk[nmax + 2]; int stktopp;
void getconvexhull(){
    for(int i = 2; i <= n; i++){
        if(a[1] > a[i]){
            swap(a[1], a[i]);
        }
    }

    sort(a + 2, a + 1 + n, [](pii a0, pii a1){
        if(crossproduct(a[1], a0, a1) == 0)
            return a0 < a1; ///idk if relevant
        return (crossproduct(a[1], a0, a1) < 0);
    });

    stk[++stktopp] = a[1];
    stk[++stktopp] = a[2];

    for(int i = 3; i <= n; i++){
        for(; stktopp >= 2 && crossproduct(stk[stktopp - 1], stk[stktopp], a[i]) >= 0; stktopp--);
        stk[++stktopp] = a[i];
    }

    for(n = 0; stktopp >= 1; stktopp--){
        a[++n] = stk[stktopp];
    }

    return;
}

/// ---> no overflow problems <--- ///
int64_t getdistpoints(pii a0, pii a1){
    return 1ll * (a0.x - a1.x) * (a0.x - a1.x) + 1ll * (a0.y - a1.y) * (a0.y - a1.y);
}

int myabs(int xx){ return ((xx < 0) ? -xx : xx); }
int64_t myabs(int64_t xx){ return ((xx < 0) ? -xx : xx); }

int64_t getmaxdistedge(pii a0, pii a1, int idx){
    int64_t maxarea = 0; ///we only need the maximum one :)

    for(int i = 1; i <= n; i++){
        maxarea = max(maxarea, myabs(crossproduct(a0, a1, a[i])));
    }

    return maxarea;
}

int64_t getlengthedge(pii a0, pii a1, int idx){
    int dxx = a1.x - a0.x, dyy = a1.y - a0.y;
    int64_t sumsq = 1ll * dxx * dxx + 1ll * dyy * dyy;

    int64_t mintt = 0, maxtt = sumsq;

    for(int i = 1; i <= n; i++){
        int64_t tt = (1ll * (a[i].x - a0.x) * dxx + 1ll * (a[i].y - a0.y) * dyy);

        mintt = min(mintt, tt); maxtt = max(maxtt, tt);
    }

    return (maxtt - mintt);
}

int main(){

    in>>n; if(n == 1){ out<<"0.00\n"; return 0; }

    for(int i = 1; i <= n; i++){
        in>>a[i].x>>a[i].y;
    }

    getconvexhull();

    a[n + 1] = a[1];

    long double minarea = 1e18;
    for(int i = 1; i <= n; i++){
        ///we choose an edge to be (a[i], a[i + 1])
        ///we know the dist * base = |cross product|
        ///so that means we need to compute the minimum area for this

        int64_t maxdistfromedge = getmaxdistedge(a[i], a[i + 1], i);
        int64_t maxlengthedge = getlengthedge(a[i], a[i + 1], i);
        minarea = min(minarea, (long double)maxdistfromedge / getdistpoints(a[i], a[i + 1]) * maxlengthedge);
    }

    minarea = (double)(floor(minarea * 100)) / 100;
    out<<fixed<<setprecision(2)<<minarea<<"\n";

    return 0;
}