Cod sursa(job #68637)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 28 iunie 2007 19:09:37
Problema Rubarba Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.89 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;

#define maxn 100010
#define db double
#define maxv 10000000
#define Cross_Product(x1,y1,x2,y2,x3,y3) (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)
#define dist(x,y,a,b,c) (a*x+b*y+c)/sqrt(a*a+b*b)
#define maxarie 1000000000000LL

int n,l,m;
int a[2*maxn],b[2*maxn],p[maxn];
int x[maxn],y[maxn],sx[maxn],sy[maxn];
db sol;

int cmp(int x,int y)
{
    return (b[x]<b[y]) || ((b[x]==b[y]) && (a[x]<a[y]));
}

int cmp2(int x,int y)
{
    return (b[x]>b[y]) || ((b[x]==b[y]) && (a[x]>a[y]));
}

inline db tg(db x1,db y1,db x2,db y2)
{
     if (x1==x2) return maxv;
     else return (y1-y2)/(x1-x2);
}

void Graham_Scan()
{
     int i,aux;
     l=2;
     x[1]=a[p[1]];
     x[2]=a[p[2]];
     y[1]=b[p[1]];
     y[2]=b[p[2]];
     
     for (i=3;i<=n;i++)
     {
         aux=Cross_Product(x[l-1],y[l-1],x[l],y[l],a[p[i]],b[p[i]]);
         
         while ((aux<=0) && (l>1))
         {
               l--;
               aux=Cross_Product(x[l-1],y[l-1],x[l],y[l],a[p[i]],b[p[i]]);
         }
         
         l++;
         x[l]=a[p[i]];
         y[l]=b[p[i]];
     }
}

void Convex_Hull()
{
     int i;
     
     for (i=1;i<=n;i++) p[i]=i;
     sort(p+1,p+n+1,cmp);
     
     Graham_Scan();
     
     for (i=1;i<l;i++) 
     {
         m++;
         sx[m]=x[i];
         sy[m]=y[i];
     }
     
     for (i=1;i<=n;i++) p[i]=i;
     sort(p+1,p+n+1,cmp2);
     
     Graham_Scan();
     
     for (i=1;i<l;i++) 
     {
         m++;
         sx[m]=x[i];
         sy[m]=y[i];
     }
     
     n=m;
     for (i=1;i<=n;i++) 
     {
         a[i]=sx[i];
         b[i]=sy[i];
         a[i+n]=sx[i];
         b[i+n]=sy[i];
     }
     a[2*n+1]=a[1];
     b[2*n+1]=b[1];
}

void make_drepte(int x1,int y1,int x2,int y2,db &a1,db &b1,db &c1,db &a2,db &b2,db &c2)
{
     db x,y;
     a1=tg(x1,y1,x2,y2);
     if (a1==0) a2=-maxv;
     else a2=-1/a1;
     b1=b2=-1;
     c1=y1-x1*a1;         
     x=(x1+x2)/2;
     y=(y1+y2)/2;
     c2=y-x*a2;
}

int main()
{
    freopen("rubarba.in","r",stdin);
    freopen("rubarba.out","w",stdout);
    
    int i,j;
    db a1,b1,c1,a2,b2,c2,max1,max2,max3,aux;
    
    scanf("%d ",&n);
    for (i=1;i<=n;i++) scanf("%d %d ",&a[i],&b[i]);
    
    Convex_Hull();
    
    sol=maxarie;
    
    for (i=1;i<=n;i++) 
    {
        make_drepte(a[i],b[i],a[i+1],b[i+1],a1,b1,c1,a2,b2,c2);     
        
        max1=0,max2=0,max3=0;
        
        for (j=i;j<n+i;j++)
        {
            aux=fabs(dist(a[j],b[j],a1,b1,c1));
            if (aux>max1) max1=aux;
            aux=dist(a[j],b[j],a2,b2,c2);
            if (aux>max2) max2=aux;
            if (aux<max3) max3=aux;
        }      
        
        aux=max1*(max2-max3);
        if (aux<sol) sol=aux;
    }
    
    printf("%lf\n",sol);
    
    return 0;
}