Cod sursa(job #953046)

Utilizator primulDarie Sergiu primul Data 24 mai 2013 18:23:43
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3 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;
}