Cod sursa(job #2705344)

Utilizator stefantagaTaga Stefan stefantaga Data 12 februarie 2021 13:53:40
Problema Rubarba Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("rubarba.in");
ofstream g("rubarba.out");
struct wow
{
    long double x,y;
}v[100005],stanga,dreapta;
int st[100005],n,q,i,ok[100005];
bool compare (wow a,wow b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
long double determinant (wow a,wow b,wow c)
{
    return a.x*b.y+b.x*c.y+a.y*c.x-a.y*b.x-b.y*c.x-a.x*c.y;
}
long double distanta (wow a,wow b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
wow v2[100005];
int q2,j;
long double minim,maximx,minimx,panta,panta2,b,b2,xfin,yfin,inalt,dist,lungime;
int main()
{
    f>>n;
    for (i=1;i<=n;i++)
    {
        f>>v[i].x>>v[i].y;
    }
    sort (v+1,v+n+1,compare);
    st[1]=1;
    st[2]=2;
    q=2;
    for (i=3;i<=n;i++)
    {
        while (q>1&&determinant(v[st[q-1]],v[st[q]],v[i])>=0)
        {
            ok[st[q]]=0;
            st[q]=0;
            q--;
        }
        st[++q]=i;
        ok[i]=1;
    }
    for (i=n;i>=1;i--)
    {
        if (ok[i]==0)
        {
            while (q>1&&determinant(v[st[q-1]],v[st[q]],v[i])>=0)
            {
                ok[st[q]]=0;
                st[q]=0;
                q--;
            }
            st[++q]=i;
            ok[i]=1;
        }
    }
    q--;
    for (i=1;i<=q;i++)
    {
        v2[++q2]=v[st[i]];
    }
    v2[q2+1]=v2[1];
    q2++;
    minim=1e9;
    for (i=1;i<=q2;i++)
    {
        inalt=0;
        minimx=1e9;
        maximx=0;
        if (v2[i].x<=v2[i+1].x)
        {
            stanga=v2[i];
            dreapta=v2[i+1];
        }
        else
        {
            stanga=v2[i+1];
            dreapta=v2[i];
        }
        for (j=1;j<=q2-1;j++)
        {
            if (v2[i].x==v2[i+1].x)
            {
                dist=v2[j].x-v2[i].x;
                xfin=v2[i].x;
                yfin=v2[j].y;
            }
            else
            {
                panta=(v2[i].y-v2[i+1].y)/(v2[i].x-v2[i+1].x);
                b=v2[i].y-panta*v2[i].x;
                panta2=-1/panta;
                b2=v2[j].y-panta2*v2[j].x;
                xfin=(b2-b)/(panta-panta2);
                yfin=panta*xfin+b;
                dist=distanta(wow{xfin,yfin},v2[j]);
            }
            inalt=max(inalt,dist);
            if (xfin<=stanga.x)
            {
                stanga=wow{xfin,yfin};
            }
            if (xfin>=dreapta.x)
            {
                dreapta=wow{xfin,yfin};
            }
        }
        lungime=distanta(stanga,dreapta);
        if (inalt*lungime<minim)
        {
            minim=inalt*lungime;
        }
    }
    g<<fixed<<setprecision(2)<<minim;
    return 0;
}