Cod sursa(job #2039187)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 14 octombrie 2017 12:32:11
Problema Rubarba Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.15 kb
#include<bits/stdc++.h>
#define maxN 100005
#define eps 0.000000000001
using namespace std;

pair<long long,long long> v[maxN];
long long n,st[maxN],vf,leftmost,rightmost,upmost;
long double ans=0.0;
pair<long long,long long> pr[maxN];
inline long double Determ(pair<long long,long long> a,pair<long long,long long> b,pair<long long,long long> c)
{
    long double det=(long double)((c.first-a.first)*(b.second-a.second)-(b.first-a.first)*(c.second-a.second));
    return det;
}

inline long double Dist(pair<long long,long long> a,pair<long long,long long> b)
{
    long double d=(a.second-b.second)*(a.second-b.second)+(a.first-b.first)*(a.first-b.first);
    d=sqrt((long double)d);
    return d;
}
inline long double SqDist(pair<long long,long long> a,pair<long long,long long> b)
{
    long double d=(a.second-b.second)*(a.second-b.second)+(a.first-b.first)*(a.first-b.first);
    //d=sqrt((long double)d);
    return d;
}

inline bool Egal(long double a,long double b)
{
    if(fabs(a-b)<eps) return 1;
    return 0;
}
inline bool cmp(pair<long long,long long> a,pair<long long,long long> b)
{
    long double det=Determ(v[1],a,b);
    if(det==0) return Dist(v[1],a)<Dist(v[1],b);
    return det>0;
}

inline long double arie(pair<long long,long long> a,pair<long long,long long> b,pair<long long,long long> c)
{
    long double det;
    det=Determ(a,b,c);
    det=fabs(det);
    return 0.5*det;
}

inline void BuildConvexHull()
{
    long long best=1;
    for(long long i=2;i<=n;i++)
    {
        if(v[i].first<v[best].first || (v[i].first==v[best].first && v[i].second<v[best].second)) best=i;
    }
    swap(v[1],v[best]);
    st[++vf]=1;
    sort(v+2,v+n+1,cmp);
    st[++vf]=2;
    for(int i=3;i<=n;i++)
    {
        while(vf>=2 && Determ(v[st[vf-1]],v[st[vf]],v[i])<=0) vf--;
        st[++vf]=i;
    }
}

inline long double Inaltime(pair<long long,long long> a,pair<long long,long long> b,pair<long long,long long> c)
{
    long double s,d;
    s=arie(a,b,c);
    d=Dist(a,b);
    return (2.0*s)/d;
}

inline long double angle(pair<long long,long long> a,pair<long long,long long> b,pair<long long,long long> c)
{
    long double d1,d2,d3;
    d1=SqDist(a,c);
    d2=SqDist(a,b);
    d3=SqDist(b,c);
    if(d1>d2+d3) return -1;
    return 1;
   // double ang=(d2*d2+d3*d3-d1*d1)/(2.0*d2*d3);
    //return ang;
}
inline long double DistLine(pair<long long,long long> a,pair<long long,long long> b,pair<long long,long long> d,pair<long long,long long> c)
{
    if(a.second==b.second)
    {
        return abs(c.first-d.first);
    }
        else
    if(a.first==b.first)
    {
        return abs(c.second-d.second);
    }
        else
    {
        long double m,m1,n1,xM,yM;
        m=(1.0*(a.second-b.second))/(1.0*(a.first-b.first));
        m1=-(1.0*(a.first-b.first))/(1.0*(a.second-b.second));
        n1=c.second-m1*c.first;
        xM=d.first;
        yM=d.second;

        long double dist=fabs(m1*xM-yM+n1)/sqrt((long double)1.0+m1*m1);

        return dist;
    }
}
inline void BruteForce()
{
    rightmost=2;
    leftmost=1;
    int st=vf,dr=2;
    while(v[dr+1].first>v[dr].first) rightmost=++dr;
    long double best=0.0;
    int pos=0;
    for(int i=3;i<=n;i++)
    {
        long double s=arie(v[1],v[2],v[i]);
        if(s>best)
        {
            best=s;
            pos=i;
        }
    }
    upmost=pos;
    leftmost=n;
    long double x=angle(v[n],v[1],v[2]);
   // cerr<<x<<'\n';
    if(angle(v[n],v[1],v[2])==-1) leftmost=n;
        else leftmost=1;
    if(angle(v[3],v[2],v[1])==-1) rightmost=3;
        else rightmost=2;
    long double h=Inaltime(v[1],v[2],v[upmost]);
    long double L=DistLine(v[1],v[2],v[leftmost],v[rightmost]);
    ans=h*L;
}
ifstream fin("rubarba.in");
ofstream fout("rubarba.out");
int main()
{
   // scanf("%lld",&n);
    fin>>n;
    for(int i=1;i<=n;i++)
    {
     //   scanf("%lld%lld",&v[i].first,&v[i].second);
        fin>>v[i].first>>v[i].second;
    }
    sort(v+1,v+n+1);
    int dn=0;
    for(int i=1;i<=n;i++)
    {
        if(i==1 || v[i]!=v[i-1]) pr[++dn]=v[i];
    }
    for(int i=1;i<=dn;i++) v[i]=pr[i];
    n=dn;
    BuildConvexHull();
    for(int i=1;i<=vf;i++)
    {
        pr[i]=v[st[i]];
    }
    for(int i=1;i<=n;i++)
    {
        v[i]=pr[i];
    }
    n=vf;
    BruteForce();

    for(int i=2;i<=n;i++)
    {
        int l,r;
        l=i;
        r=(i+1);
        if(r>n) r=1;
        if(upmost==l)
        {
            upmost+=2;
            if(upmost>n) upmost-=n;
        }
        while(arie(v[l],v[r],v[(upmost+1)-n*(upmost==n)])-arie(v[l],v[r],v[upmost])>=-eps) upmost=upmost+1-n*(upmost==n);
        leftmost=i-1;

        if(angle(v[leftmost],v[l],v[r])==-1) leftmost=i-1;
            else leftmost=i;
        rightmost=r+1;
        if(rightmost>n) rightmost=1;
        if(angle(v[l],v[r],v[rightmost])==-1) rightmost=rightmost;
            else rightmost=r;
        long double h=Inaltime(v[l],v[r],v[upmost]);
        long double L=DistLine(v[l],v[r],v[leftmost],v[rightmost]);
        ans=min(ans,h*L);
    }

    fout<<setprecision(3)<<fixed<<ans<<'\n';

    return 0;
}