Cod sursa(job #3291927)

Utilizator shisuiShisui shisui Data 6 aprilie 2025 12:02:38
Problema Rubarba Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.89 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
//#include <bits/stdc++.h>
#define in fin
#define out fout

using namespace std;
using ll = long long;
using db = double;

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

struct punct{
    db x, y;

    bool operator == (punct b) const {
        return (x == b.x && y == b.y);
    }
};

db det(punct a, punct b, punct c){
    a.x -= c.x;
    a.y -= c.y;
    b.x -= c.x;
    b.y -= c.y;
    return (a.x * b.y - b.x * a.y);
}

double eps = 0.000001;
bool egal (db a, db b) {
    if (a + eps >= b && a - eps <= b) {
        return true;
    }
    return false;
}

punct start;
bool cmp(const punct& a, const punct& b){
    if (a == start) return true;
    if (b == start) return false;
    if (egal(a.x, start.x) && egal(b.x, start.x)) {
        return a.y > b.y;
    }
    return (det(start, a, b) > 0);
}

db d(const punct& a, const punct& b){
    // cout << "A = ( " << a.x << " , " << a.y << " ) B = ( " << b.x << " , " << b.y << " ) d = " << abs(a.x - b.x) * abs(a.x - b.x) + abs(a.y - b.y) * abs(a.y - b.y) << '\n';
    return sqrt( (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) );
}

punct pr(punct A, punct B, punct C){
    if(egal(A.x, B.x)) {
        punct prr;
        prr.x = A.x;
        prr.y = C.y;
        return prr;
    }

    if(egal(A.y, B.y)) {
        punct prr;
        prr.x = C.x;
        prr.y = A.y;
        return prr;
    }

    db a = (A.y - B.y) / (A.x - B.x);
    db b = A.y - a * A.x;

    db c = ((db)-1) / a;
    db d = C.y - C.x * c;

    db xp = (C.y * a + C.x - b * a) / (a * a + 1);
    db yp = c * xp + d;

    punct prr;
    prr.x = xp;
    prr.y = yp;

    return prr;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n; in >> n;
    punct v[n];

    start.x = start.y = 1000000000;
    for(int i = 0; i < n; i++){
        in >> v[i].x >> v[i].y;
        if(v[i].x < start.x || (egal(v[i].x, start.x) && v[i].y < start.y)) start = v[i];
    }

    for (int i = 1; i < n; ++i) {
        if (egal(v[i], start)) {
            swap(v[i], v[0]);
        }
    }

    sort(v + 1, v + n, cmp);

    // cout << "v : \n";
    // for(int i = 0; i < n; i++) cout << v[i].x << " " << v[i].y << '\n';

    vector< punct > infs;
    infs.push_back(start);

    for(int i = 0; i < n; i++){
        while(infs.size() >= 2){
            const punct& a = infs[infs.size() - 2];
            const punct& b = infs[infs.size() - 1];

            if(det(a, b, v[i]) < 0){
                infs.pop_back();
            } else {
                break;
            }
        }
        infs.push_back(v[i]);
    }

    // cout << "infs : \n";
    // for(int i = 0; i < infs.size(); i++) cout << infs[i].x << " " << infs[i].y << '\n';

    infs.push_back(infs[0]);
    db mini = 10000000000000;
    for(int i = 0; i + 1 < infs.size(); i++){
        db inaltime = 0;

        punct st, dr;
        st.x = st.y = 1000000000;
        dr.x = dr.y = -1000000000;
        for(int k = 0; k < infs.size(); k++){
            punct p = pr(infs[i], infs[i + 1], infs[k]);
            inaltime = max(inaltime, d( infs[k], p ));

            if(p.x < st.x || (egal(p.x, st.x) && p.y < st.y)) st = p;
            if(p.x > dr.x || (egal(p.x, dr.x) && p.y > dr.y)) dr = p;
        }

        // cout << "Alegem ( " << infs[i].x << " , " << infs[i].y << " ) si ( " << infs[i + 1].x << " , " << infs[i + 1].y << " )\n";
        // cout << "  -- > inaltime = " << inaltime << '\n';

        punct left = pr(infs[i], infs[i + 1], st);
        punct right = pr(infs[i], infs[i + 1], dr);

        mini = min(mini, inaltime * d(left, right));
        // cout << "  -- > left = " << left.x << " , " << left.y << '\n';
        // cout << "  -- > right = " << right.x << " , " << right.y << '\n';
        // cout << "  -- > d = " << d(left, right) << '\n';
    }

    out << fixed << setprecision(2) << mini << '\n';

    return 0;
}