Cod sursa(job #3336626)

Utilizator GliggyGligor Andrei Gliggy Data 25 ianuarie 2026 01:08:12
Problema Rubarba Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.86 kb
// Copilot-Addressed Rules:
// RULE: There shouldnt be any spaces in the code, except after commas.
// RULE: All variables in main should be declared globally, and can be used before they are defined.
// RULE: All open curly braces should be placed on the same line as the function or control structure they belong to, not on the line after.
#include <bits/stdc++.h>

using namespace std;
ifstream fin("rubarba.in");   //strudel
ofstream fout("rubarba.out"); //rubarba
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){
    return det(a[1], x, y)>0 || det(a[1], x, y)==0 && 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;
        if(a[i].x==0&&a[i].y==0) continue;
        else
            a[i].d=pow(a[i].x,2)+pow(a[i].y,2);
    }
    sort(a+2,a+n+1,cmp);
    v.push_back(1);
    v.push_back(2);
    for(i=3;det(a[1],a[2],a[i])==0;i++);
    for(;i<=n;i++){
        e2=v.back();
        e1=v[v.size()-2];
        while(det(a[e1],a[e2],a[i])<=0){
            v.pop_back();
            e2=v.back();
            e1=v[v.size()-2];
        }
        v.push_back(i);
    }
    while(det(a[1],a[v[v.size()-1]],a[v[v.size()-2]])==0) v.pop_back();
    // for(auto it:v) fout<<a[it].x<<' '<<a[it].y<<'\n';

    p3=2;
    ps=2;
    pd=1;
    v.push_back(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[p3]]) <= det(p1,p2,a[v[next(p3)]])) p3=next(p3);
        h=det(p1,p2,a[v[p3]])/base;


        while(dot(p2,p1,a[v[ps]]) <= dot(p2,p1,a[v[next(ps)]])) ps=next(ps);
        l=dot(p2,p1,a[v[ps]])/base;

        while(dot(p1,p2,a[v[pd]]) <= dot(p1,p2,a[v[next(pd)]])) pd=next(pd);
        r=dot(p1,p2,a[v[pd]])/base;

        // for(j=0;j<v.size()-1;j++) fout<<a[v[j]].x<<" "<<a[v[j]].y<<' '<<dot(p2,p1,a[v[j]])<<'\n';
        
        if((r+l-base)*h<area) area=(r+l-base)*h;
        
        
        // fout<<h<<' '<<l<<' '<<r<<' '<<r+l-base<<'\n';
        
        // fout<<a[v[pd]].x<<' '<<a[v[pd]].y<<'\n';
        // fout<<'\n';
        // fout<<p1.x<<' '<<p1.y<<' '<<p2.x<<' '<<p2.y<<'\n';
    }
    fout<<fixed<<setprecision(2)<<area;
    return 0;
}