Cod sursa(job #3226998)

Utilizator andiRTanasescu Andrei-Rares andiR Data 23 aprilie 2024 21:17:37
Problema Rubarba Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.56 kb
// Author: Tanasescu Andrei-Rares
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>
#include <cassert>

#pragma GCC optimize("O3")

#define x first
#define y second
#define pb push_back
#define pf push_front

using namespace std;

ifstream fin ("rubarba.in");
ofstream fout ("rubarba.out");

typedef long long ll;
typedef pair<ll, ll> pii;

const ll Nmax=1e6+5, inf=(ll)2e18+5;

ll n, sz;
ll hull[Nmax];
pii v[Nmax];

ll det(pii a, pii b, pii c){
    return ((ll)b.x-a.x)*(c.y-a.y)-((ll)b.y-a.y)*(c.x-a.x);
}
ll dist(pii a, pii b){
    return ((ll)a.x-b.x)*(a.x-b.x)+((ll)a.y-b.y)*(a.y-b.y);
}
bool cmp(pii a, pii b){
    if (det(v[0], a, b)==0)
        return dist(v[0], a)>dist(v[0], b);
    return det(v[0], a, b)>0;
}
long double solve_eq(pii P0, pii P2, int a, int b){
    if (a==0)
        return ((long double)P2.y-P0.y)/b;
    if (b==0)
        return ((long double)P2.x-P0.x)/a;
    return (-b*(P0.y-P2.y)-a*(P0.x-P2.x))/((long double)a*a+b*b);
}
long double getL(pii st, pii dr, int ind){
    return abs(det(st, dr, v[hull[ind]]))/sqrt(dist(st, dr));
}

long double sol=inf;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    fin>>n;
    if (n<=2){
        fout<<fixed<<setprecision(2)<<0;
        return 0;
    }

    for (int i=0; i<n; i++)
        fin>>v[i].x>>v[i].y;
    ll ind=0;
    for (int i=1; i<n; i++)
        if (v[i].y<v[ind].y)
            ind=i;
        else if (v[i].y==v[ind].y && v[i].x<v[ind].x)
            ind=i;
    swap(v[0], v[ind]);
    sort(v+1, v+n, cmp);
    int crt=2;
    while (crt!=n && det(v[0], v[1], v[crt])==0)
        crt++;
    reverse(v+1, v+crt);

    hull[0]=0;
    hull[1]=1;
    sz=2;
    for (int i=2; i<n; i++){
        while (sz!=2 && det(v[i], v[hull[sz-2]], v[hull[sz-1]])<=0){
            sz--;
        }
        hull[sz++]=i;
    }
    pii st=v[hull[0]];
    pii dr=v[hull[1]];

    ll indh=0, indst=0, inddr=0, a=v[1].x-v[0].x, b=v[1].y-v[0].y;
    long double L=0, l=0, r=0;
    for (int i=1; i<sz; i++){
        if (abs(det(st, dr, v[hull[i]]))>abs(det(st, dr, v[hull[indh]]))){
            indh=i;
            L=abs(det(st, dr, v[hull[i]]))/sqrt(dist(st, dr));
        }
        long double alpha=solve_eq(st, v[hull[i]], a, b);
        if (alpha>r){
            r=alpha;
            inddr=i;
        }
        if (alpha<l){
            l=alpha;
            indst=i;
        }
    }
    sol=L*(r-l)*sqrt(dist(v[0], v[1]));

    for (int i=1; i<sz; i++){
        st=v[hull[i]];
        dr=v[hull[(i+1)%sz]];

        if (i==indh)
            indh=(indh+1)%sz;
        if (i==indst)
            indst=(indst+1)%sz;
        if (i==inddr)
            inddr=(inddr+1)%sz;

        L=abs(det(st, dr, v[hull[indh]]))/sqrt(dist(st, dr));
        a=dr.x-st.x;
        b=dr.y-st.y;
        l=solve_eq(st, v[hull[indst]], a, b);
        r=solve_eq(st, v[hull[inddr]], a, b);

        while (getL(st, dr, (indh+1)%sz)>L){
            L=getL(st, dr, (indh+1)%sz);
            indh=(indh+1)%sz;
        }
        while (solve_eq(st, v[hull[(indst+1)%sz]], a, b)<l){
            l=solve_eq(st, v[hull[(indst+1)%sz]], a, b);
            indst=(indst+1)%sz;
        }
        while (solve_eq(st, v[hull[(inddr+1)%sz]], a, b)>r){
            r=solve_eq(st, v[hull[(inddr+1)%sz]], a, b);
            inddr=(inddr+1)%sz;
        }
        if (L*(r-l)*sqrt(dist(st, dr))<sol)
            sol=L*(r-l)*sqrt(dist(st, dr));
    }
    fout<<fixed<<setprecision(3)<<sol;

    return 0;
}