Cod sursa(job #725698)

Utilizator GrimpowRadu Andrei Grimpow Data 26 martie 2012 21:42:39
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.99 kb
#include<fstream>
#include<algorithm>
#include<cmath>
#define x first
#define y second

using namespace std;

const char iname[]="rubarba.in";
const char oname[]="rubarba.out";
const int maxn=100005;

ifstream f(iname);
ofstream g(oname);

typedef pair<int,int> point;

point a[maxn];

int i,j,n,k,step,h[maxn*2],been[maxn],maxd,maxl,maxr;

long long area(point a,point b,point c)
{
    long long areax=1LL*a.x*(b.y-c.y)+1LL*b.x*(c.y-a.y)+1LL*c.x*(a.y-b.y);
    return areax;
}

long long mod(long long a)
{
    if(a<0)
        return -a;
    return a;
}

long long dep(point a,point b,point c)
{
    long long depx =  -1LL*(a.x-b.x)*(a.x-b.x)-1LL*(a.y-b.y)*(a.y-b.y)-1LL*(b.x-c.x)*(b.x-c.x)-1LL*(b.y-c.y)*(b.y-c.y)+1LL*(c.x-a.x)*(c.x-a.x)+1LL*(c.y-a.y)*(c.y-a.y);
    return depx;
}

double dis(point a,point b)
{
    return sqrt(1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y));
}

bool fcomp(point a,point b)
{
    if(a.y!=b.y)
        return a.y<b.y;
    return a.x<b.x;
}

double minarea=1e26,areax;

int main()
{
    f>>n;
    if(n<=2)
    {
        g<<"0.0\n";
        f.close();
        g.close();

        return 0;
    }
    for(i=1;i<=n;++i)
        f>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,fcomp);
    step=1;
    h[0]=1;
    h[1]=2;
    k=1;
    been[2]=1;
    i=3;
    while(been[1]==0)
    {
        while(been[i])
        {
            i+=step;
            if(i==n)
                step=-1;
        }
        while(k&&(area(a[h[k-1]],a[h[k]],a[i])<0||(area(a[h[k-1]],a[h[k]],a[i])==0&&dis(a[h[k-1]],a[i])>dis(a[h[k-1]],a[h[k]]))))
            been[h[k--]]=0;
        been[h[++k]=i]=1;
    }
    if(a[1]==a[n])
    {
        g<<"0.0\n";
        f.close();
        g.close();

        return 0;
    }
    if(k==1)
        h[++k]=n;
    for(i=1;i<=k;++i)
        h[i+k]=h[i];

    for(i=0;i<k;++i)
    {
        maxd=maxr=maxl=0;
        for(step=1;step<k;step<<=1);
        for(j=i+1;step;step>>=1)
            if(j+step<i+k&&area(a[h[i]],a[h[i+1]],a[h[j+step]])>=area(a[h[i]],a[h[i+1]],a[h[j+step-1]]))
                j+=step;
        maxd=j;
        for(step=1;step<k;step<<=1);
        for(j=i+1;step;step>>=1)
            if(j+step<=maxd&&dep(a[h[i]],a[h[i+1]],a[h[j+step]])>=dep(a[h[i]],a[h[i+1]],a[h[j+step-1]]))
                j+=step;
        maxr=j;
        for(step=1;step<k;step<<=1);
        for(j=maxd;step;step>>=1)
            if(j+step<=i+k&&dep(a[h[i+1]],a[h[i]],a[h[j+step]])>=dep(a[h[i+1]],a[h[i]],a[h[j+step-1]]))
                j+=step;
        maxl=j;
        areax=dep(a[h[i]],a[h[i+1]],a[h[maxr]])+dep(a[h[i+1]],a[h[i]],a[h[maxl]]);
        areax/=2.0*dis(a[h[i]],a[h[i+1]]);
        areax+=dis(a[h[i]],a[h[i+1]]);
        areax*=(1.0*area(a[h[i]],a[h[i+1]],a[h[maxd]]))/dis(a[h[i]],a[h[i+1]]);
        if(areax<minarea)
            minarea=areax;
    }

    g.setf(ios::fixed,ios::floatfield);
    g.precision(2);
    g<<minarea<<"\n";

    f.close();
    g.close();

    return 0;
}