Cod sursa(job #3310262)

Utilizator gugalcromMuntoiu Vlad-Ioan gugalcrom Data 12 septembrie 2025 14:28:46
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.78 kb
#include <ios>
#include <iostream>
#include <fstream>
#include <limits>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>

using namespace std;
struct Punct {
    double x, y;
    Punct operator-(const Punct &p) const {
        return {x - p.x, y - p.y};
    }
    Punct operator+(const Punct &p) const {
        return {x + p.x, y + p.y};
    }
    Punct operator*(double t) const {
        return {x * t, y * t};
    }
    double operator^(const Punct &p) const {
        return x*p.y - y*p.x;
    }
};

vector<Punct> infasuratoare(vector<Punct> poligon) {
    map<double, Punct> p;
    int imn;
    Punct mn{10e12, 10e12};
    for(int i=0; i<poligon.size(); ++i) {
        auto &punct = poligon[i];
        if(punct.y < mn.y || (punct.y == mn.y && punct.x < mn.x)) {
            mn = punct;
            imn = i;
        }
    }
    for(int i=0; i<poligon.size(); ++i) {
        auto &punct = poligon[i];
        if(imn != i) {
            double unghi = atan2(punct.y-mn.y, punct.x-mn.x);
            if(!p.count(unghi)) {
                p[unghi] = punct;
            } else {
                double d1 = (p[unghi].x-mn.x)*(p[unghi].x-mn.x) + (p[unghi].y-mn.y)*(p[unghi].y-mn.y);
                double d2 = (punct.x-mn.x)*(punct.x-mn.x) + (punct.y-mn.y)*(punct.y-mn.y);
                if(d2 > d1) {
                    p[unghi] = punct;
                }
            }
        }
    }

    vector<Punct> stiva;
    stiva.push_back(mn);

    for(auto &[unghi, punct] : p) {
        while(stiva.size() >= 2) {
            Punct A = stiva[stiva.size()-2];
            Punct B = stiva[stiva.size()-1];
            long double k = (B.x - A.x)*(punct.y - A.y) - (B.y - A.y)*(punct.x - A.x);
            if(k <= 0) {
                stiva.pop_back();
            } else {
                break;
            }
        }
        stiva.push_back(punct);
    }

    return stiva;
}

double lungime(Punct A, Punct B) {
    return sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}

double ariaHeron(double AB, double AC, double BC) {
    double s = (AB+AC+BC)/2;
    return sqrt(s*(s-AB)*(s-BC)*(s-AC));
}

double distantaPunctDreapta(Punct P, Punct A, Punct B) {
    double AB = lungime(A, B);
    double AP = lungime(A, P);
    double BP = lungime(B, P);
    double aria = ariaHeron(AB, AP, BP);
    return 2 * aria / AB;
}

double distantaProiectie(Punct P, Punct A, Punct B) {
    double lg = lungime(A, B);
    if(!lg) {
        return 0;
    }
    return ((P.x-A.x) * (B.x-A.x) + (P.y-A.y) * (B.y-A.y)) / lg;
}

double dreptunghi(vector<Punct> infasuratoare) {
    double mn = numeric_limits<double>::max();

    int N = infasuratoare.size();

    for(int i=0; i<N; ++i) {
        Punct A = infasuratoare[i];
        Punct B = infasuratoare[(i+1)%N];
        double dmx = 0;
        for(int j=0; j<N; ++j) {
            double distanta = distantaPunctDreapta(infasuratoare[j], A, B);
            if(distanta > dmx) {
                dmx = distanta;
            }
            //cout << "h " << dmx << '\n';
        }
        double stmx = numeric_limits<double>::max(), drmx = -numeric_limits<double>::max();
        for(int j=0; j<N; ++j) {
            double proiectie = distantaProiectie(infasuratoare[j], A, B);
            stmx = min(proiectie, stmx);
            drmx = max(proiectie, drmx);
            //cout << "! " << stmx << ' ' << drmx << '\n';
        }
        //cout << "!! " << dmx * (drmx-stmx) << '\n';
        mn = min(mn, dmx * (drmx-stmx));
    }

    return mn;
}

int main() {
    ifstream fin("rubarba.in");
    ofstream fout("rubarba.out");
    fout << fixed << setprecision(2);
    int N;
    fin >> N;
    vector<Punct> pt(N);
    for(int i=0; i<N; ++i) {
        fin >> pt[i].x >> pt[i].y;
    }
    auto cpt = infasuratoare(pt);
    fout << dreptunghi(cpt) << '\n';
    return 0;
}