Cod sursa(job #3032563)

Utilizator CReaper1116Shang Cheng Lin CReaper1116 Data 22 martie 2023 13:43:24
Problema Rubarba Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.29 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("rubarba.in");
ofstream fout("rubarba.out");
typedef long long ll;
struct p{
    int y,x;
}v[100000];
p operator+(p a,p b){
    return {a.y + b.y,a.x + b.x};
}
p operator-(p a,p b){
    return {a.y - b.y,a.x - b.x};
}
ll anticlock(p a,p b,p c){
    return 1ll*(c.y - b.y)*(b.x - a.x) - 1ll*(b.y - a.y)*(c.x - b.x);
}
bool sameside(p a,p b,p c,p d){
    return (anticlock(a,b,c) >= 0 && anticlock(a,b,d) >= 0) || (anticlock(a,b,c) <= 0 && anticlock(a,b,d) <= 0);
}
float dist(p a,p b,p c){
    if((float)sqrt((b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y)) == 0)return 0;
    return (float)abs((b.x - a.x)*(a.y - c.y) - (a.x - c.x)*(b.y - a.y))/(float)sqrt((b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y));
}
vector <p> lp,rp;
vector <p> hull;
int main(){
    int n,i;
    float ans = 2e9;
    fin>>n;
    if(n <= 2){
        fout<<0;
        return 0;
    }
    for(i = 0;i < n;i++){
        fin>>v[i].y>>v[i].x;
    }
    sort(v,v + n,[&](p a,p b){
         return a.y < b.y;
    });
    lp.push_back(v[0]);rp.push_back(v[0]);
    for(i = 1;i < n - 1;i++){
        if(anticlock(v[0],v[n - 1],v[i]) >= 0){
            ///left side
            while(lp.size() > 1 && anticlock(lp[lp.size() - 2],v[i],lp[lp.size() - 1]) <= 0){
                lp.pop_back();
            }
            lp.push_back(v[i]);
        }else{
            ///rightside
            while(rp.size() > 1 && anticlock(rp[rp.size() - 2],v[i],rp[rp.size() - 1]) >= 0){
                rp.pop_back();
            }
            rp.push_back(v[i]);
        }
    }
    while(lp.size() > 1 && anticlock(lp[lp.size() - 2],v[n - 1],lp[lp.size() - 1]) <= 0){
        lp.pop_back();
    }
    while(rp.size() > 1 && anticlock(rp[rp.size() - 2],v[n - 1],rp[rp.size() - 1]) >= 0){
        rp.pop_back();
    }
    rp.push_back(v[n - 1]);
    for(auto i:lp)hull.push_back(i);
    for(int i = rp.size() - 1;i >= 1;i--)hull.push_back(rp[i]);
    int opp,l,r = 0;
    n = hull.size();
    while(r < n && !sameside(hull[r],{hull[r].y + hull[0].x - hull[1].x,hull[r].x - hull[0].y + hull[1].y},hull[(r - 1 + n)%n],hull[(r + 1)%n]))r++;
    opp = 2;
    while(opp < n && !sameside(hull[opp],hull[opp] + hull[1] - hull[0],hull[opp - 1],hull[(opp + 1)%n]))opp++;
    l = opp;
    while(l < n && !sameside(hull[l],{hull[l].y + hull[0].x - hull[1].x,hull[l].x - hull[0].y + hull[1].y},hull[(l - 1 + n)%n],hull[(l + 1)%n]))l++;
    ans = min(ans,dist(hull[0],hull[1],hull[opp])*dist(hull[r],{hull[r].y + hull[0].x - hull[1].x,hull[r].x - hull[0].y + hull[1].y},hull[l]));
    for(i = 1;i < n;i++){
        while(!sameside(hull[r],{hull[r].y + hull[i].x - hull[(i+1)%n].x,hull[r].x - hull[i].y + hull[(i+1)%n].y},hull[(r - 1 + n)%n],hull[(r + 1)%n]))r++,r%=n;
        while(!sameside(hull[opp],hull[opp] + hull[(i+1)%n] - hull[i],hull[(opp - 1 + n)%n],hull[(opp + 1)%n]))opp++,opp%=n;
        while(!sameside(hull[l],{hull[l].y + hull[i].x - hull[(i+1)%n].x,hull[l].x - hull[i].y + hull[(i+1)%n].y},hull[(l - 1 + n)%n],hull[(l + 1)%n]))l++,l%=n;
        ans = min(ans,dist(hull[i],hull[(i + 1)%n],hull[opp])*dist(hull[r],{hull[r].y + hull[i].x - hull[(i+1)%n].x,hull[r].x - hull[i].y + hull[(i+1)%n].y},hull[l]));
    }
    fout<<fixed<<setprecision(2)<<ans;
    return 0;
}