Cod sursa(job #474544)

Utilizator ionutz32Ilie Ionut ionutz32 Data 4 august 2010 00:31:46
Problema Rubarba Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.58 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int n,i,x,y,pct,stack[100005],nrs,j,st,dr;
pair<int,int> v[100005];
pair<double,double> pmin,pmax;
double sol,a2,b2,a,b,x2,y2,len,d,h;
struct cmp
{
    inline bool operator()(const pair<int,int> &a,const pair<int,int> &b)const
    {
        if (a.first==x && a.second==y)
            return 1;
        if (b.first==x && b.second==y)
            return 0;
        if (a.first==x)
            return 0;
        if (b.first==x)
            return 1;
        return (double)(a.second-y)/(a.first-x)<(double)(b.second-y)/(b.first-x);
    }
};

inline bool opus(int dr1,int dr2,int pct)
{
    if (v[dr1].first==v[dr2].first)
        return (x<=v[dr1].first && v[dr1].first<v[pct].first);
    double a,b,rez1,rezpct;
    a=double(v[dr1].second-v[dr2].second)/(v[dr1].first-v[dr2].first);
    b=v[dr1].second-a*v[dr1].first;
    rez1=a*x+b-y;
    rezpct=a*v[pct].first+b-v[pct].second;
    return ((rez1>=0 && rezpct<0) || (rez1<=0 && rezpct>0));
}

inline double dist(pair<double,double> a,pair<double,double> b)
{
    return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}

inline bool egal(double a,double b)
{
    return (abs(a-b)<0.0000000000001);
}

inline bool maimic(pair<double,double> pct1,pair<double,double> pct2)
{
    double val1,val2;
    val1=dist(pct1,v[stack[i]]);
    if (egal(val1+len,dist(pct1,v[stack[i+1]])))
        val1=-val1;
    val2=dist(pct2,v[stack[i]]);
    if (egal(val2+len,dist(pct2,v[stack[i+1]])))
        val2=-val2;
    return (val1<val2);
}

int main()
{
    freopen("rubarba.in","r",stdin);
    freopen("rubarba.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;++i)
    {
        scanf("%d %d",&x,&y);
        v[i]=make_pair(x,y);
        if (!pct || (x<v[pct].first || (x==v[pct].first && y<v[pct].second)))
            pct=i;
    }
    x=v[pct].first;
    y=v[pct].second;
    sort(v+1,v+n+1,cmp());
    stack[nrs=1]=1;
    for (i=2;i<=n;++i)
    {
        while (nrs>=3 && opus(stack[nrs],stack[nrs-1],i))
            --nrs;
        stack[++nrs]=i;
    }
    stack[nrs+1]=1;
    sol=(double)1000001*1000001;
    for (i=1;i<=nrs;++i)
    {
        st=dr=h=0;
        if (v[stack[i]].first==v[stack[i+1]].first)
        {
            for (j=1;j<=nrs;++j)
            {
                if (!st || v[stack[j]].second<v[st].second)
                    st=stack[j];
                if (!dr || v[stack[j]].second>v[dr].second)
                    dr=stack[j];
                if (abs(v[stack[j]].first-v[stack[i]].first)>h)
                    h=abs(v[stack[j]].first-v[stack[i]].first);
            }
            if ((v[dr].second-v[st].second)*h<sol)
                sol=(v[dr].second-v[st].second)*h;
        }
        else
            if (v[stack[i]].second==v[stack[i+1]].second)
            {
                for (j=1;j<=nrs;++j)
                {
                    if (!st || v[stack[j]].first<v[st].first)
                        st=stack[j];
                    if (!dr || v[stack[j]].first>v[dr].first)
                        dr=stack[j];
                    if (abs(v[stack[j]].second-v[stack[i]].second>h))
                        h=abs(v[stack[j]].second-v[stack[i]].second);
                }
                if ((v[dr].first-v[st].first)*h<sol)
                    sol=(v[dr].first-v[st].first)*h;
            }
            else
            {
                len=dist(v[stack[i]],v[stack[i+1]]);
                for (j=1;j<=nrs;++j)
                {
                    a2=-(double)(v[stack[i]].first-v[stack[i+1]].first)/(v[stack[i]].second-v[stack[i+1]].second);
                    b2=v[stack[j]].second-a2*v[stack[j]].first;
                    a=(double)(v[stack[i]].second-v[stack[i+1]].second)/(v[stack[i]].first-v[stack[i+1]].first);
                    b=v[stack[i]].second-a*v[stack[i]].first;
                    x2=(double)(b2-b)/(a-a2);
                    y2=a*x2+b;
                    if (!st || maimic(make_pair(x2,y2),pmin))
                        st=stack[j],
                        pmin=make_pair(x2,y2);
                    if (!dr || maimic(pmax,make_pair(x2,y2)))
                        dr=stack[j],
                        pmax=make_pair(x2,y2);
                    d=dist(v[stack[j]],make_pair(x2,y2));
                    if (d>h)
                        h=d;
                }
                d=dist(pmin,pmax)*h;
                if (d<sol)
                    sol=d;
            }
    }
    printf("%.2lf",sol);
    return 0;
}