Cod sursa(job #3284470)

Utilizator IleaIlea Bogdan Ilea Data 11 martie 2025 17:38:43
Problema Rubarba Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.16 kb
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
using namespace std;

#define NMAX 100001
#define INF 1000001
int n;
struct point{
    double x, y;
    friend bool operator<(point p1, point p2){
        if (p1.x==p2.x)return p1.y<p2.y;
        return p1.x<p2.x;
    }
    point operator+=(point p1){
        this->x+=p1.x;
        this->y+=p1.y;
        return *this;
    }
    point operator/=(double ii){
        this->x/=ii;
        this->y/=ii;
        return *this;
    }
} a[NMAX], w[NMAX];
vector<int> st;
bool used[NMAX];
double rem_stack(point p1, point p2, point p3){
    return ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y));
}
void conv(){
    st.push_back(1);
    st.push_back(2);
    used[2]=true;
    for (int i=3; i<=n; ++i){
        if (used[i])continue;
        while (st.size()>=2 && .0>=rem_stack(a[st[st.size()-2]], a[st[st.size()-1]], a[i])){
            used[st.back()]=false;
            st.pop_back();
        }
        used[i]=true;
        st.push_back(i);
    }
    for (int i=n; i>0; --i){
        if (used[i])continue;
        while (st.size()>=2 && .0>=rem_stack(a[st[st.size()-2]], a[st[st.size()-1]], a[i])){
            used[st.back()]=false;
            st.pop_back();
        }
        used[i]=true;
        st.push_back(i);
    }
    //st.pop_back();
}
int main(){
    freopen("rubarba.in", "r", stdin);
    freopen("rubarba.out", "w", stdout);
    cin>>n;
    for (int i=1; i<=n; ++i){
        cin>>a[i].x>>a[i].y;
    }
    sort(a+1, a+n+1);
    //for (int i=1; i<=n; ++i)cout<<i<<": "<<a[i].x<<" "<<a[i].y<<endl;
    conv();
    //cout<<endl; for (auto it:st)cout<<it<<": "<<a[it].x<<" "<<a[it].y<<endl;
    /// please explain
    double ans = INF;
    for (int i=0; i<st.size(); ++i){
        int next_i=(i+1)%st.size();
        double unghi=atan2(a[st[next_i]].y-a[st[i]].y, a[st[next_i]].x-a[st[i]].x);
        unghi=-unghi;
        double xmax=-INF, xmin=INF;
        double ymax=-INF, ymin=INF;
        for (int j=0; j<st.size(); ++j) {
            w[j].x=a[st[j]].x*cos(unghi)-a[st[j]].y*sin(unghi);
            w[j].y=a[st[j]].x*sin(unghi)+a[st[j]].y*cos(unghi);
            xmax = max(xmax, w[j].x);
            xmin = min(xmin, w[j].x);
            ymax = max(ymax, w[j].y);
            ymin = min(ymin, w[j].y);
        }
        double arie=(xmax-xmin)*(ymax-ymin);
        ans=min(ans, arie);
    }
    cout<<setprecision(2)<<fixed<<ans;
    /* sol pt calculat aria strict a infasuratoarei convexe
    point mid={.x=0, .y=0};
    for (auto it:st){
        //cout<<a[it].x<<" "<<a[it].y<<endl;
        mid+=a[it];
    }
    mid/=double(st.size());
    //cout<<mid.x<<" "<<mid.y;
    double area=.0, calc_area=[](point p1, point p2, point p3){
                        double c=p1.x*p2.y+p2.x*p3.y+p3.x*p1.y
                                -p3.x*p2.y-p1.x*p3.y-p2.x*p1.y;
                        return .5*(c<.0 ? -c : c);
                    };
    for (int i=0; i<st.size(); ++i){
        int j=(i+1)%st.size();
        area+=calc_area(a[i], a[j], mid);
    }
    cout<<setprecision(2)<<fixed<<area;
    */
    return 0;
}