Cod sursa(job #3357028)

Utilizator Lex._.Lex Guiman Lex._. Data 5 iunie 2026 09:59:09
Problema Rubarba Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.36 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#define NMAX 100000
#define x first
#define y second
using namespace std;

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

int n;
pair<long double, long double> v[NMAX+1];
bool clockwise(pair<long double, long double> a, pair<long double, long double> b, pair<long double, long double> c)
{
    long long arie=(a.y+b.y)*(b.x-a.x)+(b.y+c.y)*(c.x-b.x)+(c.y+a.y)*(a.x-c.x);
    return (arie>=0);
}

bool counterclockwise(pair<long double, long double> a, pair<long double, long double> b, pair<long double, long double> c)
{
    long long arie=(a.y+b.y)*(b.x-a.x)+(b.y+c.y)*(c.x-b.x)+(c.y+a.y)*(a.x-c.x);
    return (arie<=0);
}

long double dist(pair<long double, long double> d, pair<long double, long double> e, pair<long double, long double> f) //distanta de la punctul F la dreapta DE
{
    long double A=d.y-e.y, B=e.x-d.x, C=d.x*(e.y-d.y)-d.y*(e.x-d.x);
    return abs(A*f.x + B*f.y + C)/sqrt(A*A+B*B);
}

long double dist(pair<long double, long double> a, pair<long double, long double> b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int nr_puncte=0;
vector<pair<long double, long double>> convex_hull;
void infasuratoare_convexa()
{
    sort(v+1, v+n+1);
    vector<pair<long double, long double>> up, down;
    pair<long double, long double> a=v[1], b=v[n];
    up.push_back(a);
    down.push_back(a);
    for(int i=2; i<=n; i++)
    {
        if(i==n || clockwise(a, v[i], b))
        {
            while(up.size()>1 && !clockwise(up[up.size()-2], up[up.size()-1], v[i]))
                up.pop_back();
            up.push_back(v[i]);
        }
        if(i==n || counterclockwise(a, v[i], b))
        {
            while(down.size()>1 && !counterclockwise(down[down.size()-2], down[down.size()-1], v[i]))
                down.pop_back();
            down.push_back(v[i]);
        }
    }
    for(int i=0; i<down.size(); i++)
    {
        convex_hull.push_back(down[i]);
    }
    for(int i=up.size()-2; i>=1; i--)
    {
        convex_hull.push_back(up[i]);
    }
    nr_puncte=convex_hull.size();
    for(int i=0; i<nr_puncte; i++)
    {
        convex_hull.push_back(convex_hull[i]);
    }
}

pair<long double, long double> perpendicular(pair<long double, long double> d, pair<long double, long double> e, pair<long double, long double> f) //piciorul perpendicularei din F pe ED
{
    if(e.x==d.x) return {e.x, f.y};
    else if(e.y==d.y) return {f.x, e.y};
    long double m1=(e.y-d.y)/(e.x-d.x), n1=-d.x*m1+d.y;
    long double m2=-1/m1, n2=-f.x*m2+f.y;
    long double x=(n2-n1)/(m1-m2), y=m1*x+n1;
    return {x, y};
}

int cautare_binara(int st, int dr, pair<long double, long double> a, pair<long double, long double> b)
{
    if(st>dr) dr+=nr_puncte; 
    long double A=a.y-b.y, B=b.x-a.x, C=a.x*(b.y-a.y)-a.y*(b.x-a.x), sqr=sqrt(A*A+B*B);
    int pos=st;
    while(st<=dr)
    {
        int mij=st+(dr-st)/2;
        if(abs(A*convex_hull[mij].x + B*convex_hull[mij].y + C)/sqr < abs(A*convex_hull[mij+1].x + B*convex_hull[mij+1].y + C)/sqr)
        {
            pos=mij+1;
            st=mij+1;
        }
        else dr=mij-1;
    }
    return pos;
}

int main()
{
    in >> n;
    for(int i=1; i<=n; i++)
    {
        in >> v[i].x >> v[i].y;
    }
    infasuratoare_convexa();
    //for(auto& [x, y] : convex_hull) out << x << " " << y << "\n"; out << "\n";
    long double ans=1e15;
    for(int i=0; i<nr_puncte; i++)
    {
        int p1=cautare_binara(i+1, i, convex_hull[i], convex_hull[i+1]);
        pair<long double, long double> h=perpendicular(convex_hull[i], convex_hull[i+1], convex_hull[p1]);
        int p2=cautare_binara(p1, i, convex_hull[p1], h);
        int p3=cautare_binara(i+1, p1, convex_hull[p1], h);

        ans=min(ans, dist(convex_hull[p1], h) * (dist(h, convex_hull[p1], convex_hull[p2])+dist(h, convex_hull[p1], convex_hull[p3])));
        //out << i << ": " << convex_hull[i].x << " " << convex_hull[i].y << "\n";
        //out << p1 << ", " << p2 << ", " << p3 << "\n";
        //out << h.x << " " << h.y << " -> " << dist(convex_hull[p1], h) * (dist(h, convex_hull[p1], convex_hull[p2])+dist(h, convex_hull[p1], convex_hull[p3])) << "\n\n";
    }
    out << fixed << setprecision(2) << ans;

    return 0;
}