Cod sursa(job #3359203)

Utilizator rares89_Dumitriu Rares rares89_ Data 26 iunie 2026 03:11:09
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <bits/stdc++.h>

using namespace std;

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

struct Point {
    long double x, y;
};

int n;
vector<Point> p, h;

long double cross(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

long double cross2(Point a, Point b) {
    return a.x * b.y - a.y * b.x;
}

long double dot(Point a, Point b) {
    return a.x * b.x + a.y * b.y;
}

bool cmp(Point a, Point b) {
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

Point vec(Point a, Point b) {
    return {b.x - a.x, b.y - a.y};
}

int nxt(int x, int n) {
    x++;
    if(x == n) x = 0;
    return x;
}

int main() {
    fin >> n;

    p.resize(n);

    for(int i = 0; i < n; i++) {
        fin >> p[i].x >> p[i].y;
    }

    if(n <= 2) {
        fout << fixed << setprecision(2) << 0.0 << "\n";
        return 0;
    }

    sort(p.begin(), p.end(), cmp);

    for(int i = 0; i < n; i++) {
        while(h.size() >= 2 && cross(h[h.size() - 2], h.back(), p[i]) <= 0) {
            h.pop_back();
        }
        h.push_back(p[i]);
    }

    int sz = h.size();

    for(int i = n - 2; i >= 0; i--) {
        while(h.size() > sz && cross(h[h.size() - 2], h.back(), p[i]) <= 0) {
            h.pop_back();
        }
        h.push_back(p[i]);
    }

    h.pop_back();

    int m = h.size();

    if(m <= 2) {
        fout << fixed << setprecision(2) << 0.0 << "\n";
        return 0;
    }

    int st = 0, dr = 0, sus = 0, jos = 0;

    Point d0 = vec(h[0], h[1]);

    for(int i = 1; i < m; i++) {
        if(dot(h[i], d0) < dot(h[st], d0)) st = i;
        if(dot(h[i], d0) > dot(h[dr], d0)) dr = i;
        if(cross2(d0, h[i]) > cross2(d0, h[sus])) sus = i;
        if(cross2(d0, h[i]) < cross2(d0, h[jos])) jos = i;
    }

    long double ans = 1e100;

    for(int i = 0; i < m; i++) {
        Point d = vec(h[i], h[nxt(i, m)]);

        while(dot(h[nxt(st, m)], d) < dot(h[st], d)) {
            st = nxt(st, m);
        }

        while(dot(h[nxt(dr, m)], d) > dot(h[dr], d)) {
            dr = nxt(dr, m);
        }

        while(cross2(d, h[nxt(sus, m)]) > cross2(d, h[sus])) {
            sus = nxt(sus, m);
        }

        while(cross2(d, h[nxt(jos, m)]) < cross2(d, h[jos])) {
            jos = nxt(jos, m);
        }

        long double latime = dot(h[dr], d) - dot(h[st], d);
        long double inaltime = cross2(d, h[sus]) - cross2(d, h[jos]);
        long double len = d.x * d.x + d.y * d.y;

        ans = min(ans, latime * inaltime / len);
    }

    fout << fixed << setprecision(2) << (double)ans << "\n";

    return 0;
}