Cod sursa(job #3336623)

Utilizator GliggyGligor Andrei Gliggy Data 25 ianuarie 2026 01:04:48
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("rubarba.in");
ofstream fout("rubarba.out");
long long n,i,inf=1e9,e1,e2,p3,ps,pd,j;
double h,r,l,base,area=1e18;
long long xv=inf,yv=inf;
vector<long long> v;
struct pct{
    long long x,y;
    double d;
};
pct a[100010];
long long det(pct m,pct n,pct p){
    return m.x*(n.y-p.y)+m.y*(p.x-n.x)+n.x*p.y-p.x*n.y;
}
bool cmp(pct x,pct y){
    long long val=det(a[1],x,y);
    if(val>0) return true;
    if(val<0) return false;
    return x.d<y.d;
}
long long next(int x){
    return (x+1)%(v.size()-1);
}
long long dot(pct x,pct y,pct z){
    return (y.x-x.x)*(z.x-x.x)+(y.y-x.y)*(z.y-x.y);
}
int main(){
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>a[i].x>>a[i].y;
        if(a[i].y<yv||(a[i].y==yv&&a[i].x<xv)) xv=a[i].x,yv=a[i].y,swap(a[1],a[i]);
    }
    for(i=1;i<=n;i++){
        a[i].x-=xv,a[i].y-=yv;
        a[i].d=1.0*a[i].x*a[i].x+1.0*a[i].y*a[i].y;
    }
    sort(a+2,a+n+1,cmp);
    v.push_back(1);
    for(i=2;i<=n;i++){
        while(v.size()>=2&&det(a[v[v.size()-2]],a[v.back()],a[i])<=0) v.pop_back();
        v.push_back(i);
    }
    v.push_back(1);
    p3=1,ps=1,pd=1;
    for(i=0;i<v.size()-1;i++){
        pct p1=a[v[i]],p2=a[v[i+1]];
        base=sqrt(1.0*dot(p1,p2,p2));
        while(det(p1,p2,a[v[next(p3)]])>=det(p1,p2,a[v[p3]])) p3=next(p3);
        while(dot(p1,p2,a[v[next(pd)]])>=dot(p1,p2,a[v[pd]])) pd=next(pd);
        if(i==0) ps=p3;
        while(dot(p2,p1,a[v[next(ps)]])>=dot(p2,p1,a[v[ps]])) ps=next(ps);
        h=1.0*det(p1,p2,a[v[p3]])/base;
        r=1.0*dot(p1,p2,a[v[pd]])/base;
        l=1.0*dot(p2,p1,a[v[ps]])/base;
        if((r+l-base)*h<area) area=(r+l-base)*h;
    }
    fout<<fixed<<setprecision(2)<<area;
    return 0;
}