Cod sursa(job #2322614)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 17 ianuarie 2019 22:41:51
Problema Rubarba Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.86 kb
#include <bits/stdc++.h>
#define det(A,B,C) (A.first*B.second+B.first*C.second+C.first*A.second)-(C.first*B.second+B.first*A.second+A.first*C.second)
#define dist(A,B) (A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second)

const double mic=1e-9;

using namespace std;

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

int n,i,j,iq,k,nxt[100010];
pair<double,double> P[100010],V[100010];

double Dist1(int i,int j)
{
    double x1,y1,x2,y2,x3,y3;
    x1=V[i].first,y1=V[i].second,x2=V[nxt[i]].first,y2=V[nxt[i]].second;
    x3=V[j].first,y3=V[j].second;
    return ((x2-x1)*(x3-(x1+x2)/2.0)+(y2-y1)*(y3-(y1+y2)/2.0))/sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}

double Dist3(int i,int j)
{
    double x1,y1,x2,y2,x3,y3;
    x1=V[i].first,y1=V[i].second,x2=V[nxt[i]].first,y2=V[nxt[i]].second;
    x3=V[j].first,y3=V[j].second;
    if(x1==x2)
        return abs(x3-x1);
    double m=(y1-y2)/(x1-x2);
    double n=(x1*y2-y1*x2)/(x1-x2);
    double d=(m*x3-y3+n)/sqrt(m*m+1);
    return abs(d);
}

bool comp(pair<double,double> a,pair<double,double> b)
{
    double x=det(P[0],a,b);
    if(x> mic)return 1;
    if(x<-mic)return 0;
    if(dist(P[0],a)-dist(P[0],b)>mic)return 0;
    return 1;
}

int main()
{
    f>>n;
    f>>P[0].first>>P[0].second;
    iq=0;
    for(i=1;i<n;i++)
    {
        f>>P[i].first>>P[i].second;
        if(P[i]<P[iq])
            iq=i;
    }
    swap(P[0],P[iq]);
    sort(P+1,P+n,comp);
    V[0]=P[0],V[1]=P[1],k=1;
    for(i=2;i<n;i++)
    {
        while(det(V[k-1],V[k],P[i])<-mic&&k)
            k--;
        V[++k]=P[i];
    }
    for(i=0;i<k;i++)nxt[i]=i+1;nxt[k]=0;
    pair<double,int> dst1={Dist1(0,0),0},dst2={Dist1(0,0),0},dst3={Dist3(0,0),0};
    for(i=1;i<=k;i++)
    {
        dst1=max(dst1,{Dist1(0,i),i});
        dst2=min(dst2,{Dist1(0,i),i});
        dst3=max(dst3,{Dist3(0,i),i});
    }
//    for(i=0;i<=k;i++)
//        g<<V[i].first<<' '<<V[i].second<<'\n';
    double ans=(dst1.first-dst2.first)*dst3.first;
    for(i=1;i<=k;i++)
    {
//        g<<i-1<<' '<<dst1.second<<' '<<dst2.second<<' '<<dst3.second<<'\n';
        dst1.first=Dist1(i,dst1.second);
        dst2.first=Dist1(i,dst2.second);
        dst3.first=Dist3(i,dst3.second);
        double aux=Dist1(i,nxt[dst1.second]);
        while(aux>dst1.first)
        {
            dst1={aux,nxt[dst1.second]};
            aux=Dist1(i,nxt[dst1.second]);
        }
        aux=Dist1(i,nxt[dst2.second]);
        while(aux<dst2.first)
        {
            dst2={aux,nxt[dst2.second]};
            aux=Dist1(i,nxt[dst2.second]);
        }
        aux=Dist3(i,nxt[dst3.second]);
        while(aux>dst3.first)
        {
            dst3={aux,nxt[dst3.second]};
            aux=Dist3(i,nxt[dst3.second]);
        }
        ans=min(ans,(dst1.first-dst2.first)*dst3.first);
    }
    g<<ans;
    return 0;
}