Cod sursa(job #2676826)

Utilizator armigheGheorghe Liviu Armand armighe Data 25 noiembrie 2020 02:01:06
Problema Rubarba Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.3 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("rubarba.in");
ofstream g("rubarba.out");
int st[100002];
bool viz[100002];

struct punct
{
    long double x,y;
};
punct v[100002];

inline bool cmp(const punct &a,const punct &b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}

inline bool calc_pante(punct a,punct b,punct c)
{
    return (c.y-a.y)*(b.x-a.x)<=(b.y-a.y)*(c.x-a.x);
}

long double dist_la_patrat(punct a,punct b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

long double calc_dist(punct a,punct b)
{
    return sqrtl(dist_la_patrat(a,b));
}

long double arie(punct a,punct b,punct c)
{
    return abs((a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x)/(long double)2);
}

long double dist_sus(punct a,punct b,punct c)
{
    return 2*arie(a,b,c)/calc_dist(a,b);
}

long double dist_dr(punct a,punct b,punct c)
{
    long double h=2*arie(a,b,c)/calc_dist(a,b),dista,distb;
    distb=sqrtl(dist_la_patrat(b,c)-h*h);
    dista=sqrtl(dist_la_patrat(a,c)-h*h);
    if(dista>=calc_dist(a,b)&&dista>=distb)
        return distb;
    else
        return -distb;
}

long double dist_st(punct a,punct b,punct c)
{
    long double h=2*arie(a,b,c)/calc_dist(a,b),dista,distb;
    dista=sqrtl(dist_la_patrat(a,c)-h*h);
    distb=sqrtl(dist_la_patrat(b,c)-h*h);
    if(distb>=calc_dist(a,b)&&distb>=dista)
        return dista;
    else
        return -dista;
}

int main()
{
    int n,i,vf,pas,left=1,right=2,sus=2;
    long double sol=1000000000000,dist,p,q;
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmp);
    st[1]=1;
    st[2]=2;
    vf=2;
    viz[2]=1;
    i=3;
    pas=1;
    while(viz[1]==0)
    {
        if(viz[i]==0)
        {
            while(vf>1&&calc_pante(v[st[vf-1]],v[st[vf]],v[i])==1)
                viz[st[vf]]=0,vf--;
            st[++vf]=i;
            viz[i]=1;
        }
        if(i==n)
            pas=-1;
        i+=pas;
    }
    vf--;
    for(i=1;i<=vf;i++)
    {
        dist=dist_sus(v[st[i]],v[st[((i+1)-1)%vf+1]],v[st[sus]]);
        while(dist_sus(v[st[i]],v[st[((i+1)-1)%vf+1]],v[st[((sus+1)-1)%vf+1]])>=dist)
        {
            sus++;
            if(sus>vf)
                sus=1;
            dist=dist_sus(v[st[i]],v[st[((i+1)-1)%vf+1]],v[st[sus]]);
        }
        dist=dist_dr(v[st[i]],v[st[((i+1)-1)%vf+1]],v[st[right]]);
        while(dist_dr(v[st[i]],v[st[((i+1)-1)%vf+1]],v[st[((right+1)-1)%vf+1]])>=dist)
        {
            right++;
            if(right>vf)
                right=1;
            dist=dist_dr(v[st[i]],v[st[((i+1)-1)%vf+1]],v[st[right]]);
        }
        if(i==1)
            left=right;
        dist=dist_st(v[st[i]],v[st[((i+1)-1)%vf+1]],v[st[left]]);
        while(dist_st(v[st[i]],v[st[((i+1)-1)%vf+1]],v[st[((left+1)-1)%vf+1]])>=dist)
        {
            left++;
            if(left>vf)
                left=1;
            dist=dist_st(v[st[i]],v[st[((i+1)-1)%vf+1]],v[st[left]]);
        }
        p=dist_sus(v[st[i]],v[st[((i+1)-1)%vf+1]],v[st[sus]]);
        q=dist_st(v[st[i]],v[st[((i+1)-1)%vf+1]],v[st[left]])+calc_dist(v[st[i]],v[st[((i+1)-1)%vf+1]])+dist_dr(v[st[i]],v[st[((i+1)-1)%vf+1]],v[st[right]]);
        sol=min(sol,p*q);
    }
    g<<fixed<<setprecision(2)<<sol;
    return 0;
}