Cod sursa(job #6078)

Utilizator moga_florianFlorian MOGA moga_florian Data 16 ianuarie 2007 23:25:57
Problema Rubarba Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.81 kb
using namespace std;
#include<fstream>
#include<math.h>
#include<stdio.h>
#define nmax 100005

int x[nmax],y[nmax];
int hull[nmax],nh;
int viz[nmax];

int comp(int i,int j)
{
if(x[i]<x[j])
   return -1;
if(x[i]>x[j])
   return 1;
if(y[i]<y[j])
   return -1;
return 1;    
}

void intersc(int i,int j)
{
int aux;
aux=x[i];
x[i]=x[j];
x[j]=aux;

aux=y[i];
y[i]=y[j];
y[j]=aux;     
}

long long det(int i,int j,int k)
{
return (long long)x[i]*y[j]+(long long)x[j]*y[k]+(long long)x[k]*y[i]-
       (long long)x[k]*y[j]-(long long)y[k]*x[i]-(long long)y[i]*x[j];    
}

double maxim(double a,double b)
{
if(a>b)
  return a;
return b;       
}

int modul(int a)
{
if(a<0)
  return -a;
return a;    
}

double dist(double x1,double y1,double x2,double y2)
{
double dx,dy;
dx=x2-x1;
dy=y2-y1;
return sqrt(dx*dx+dy*dy);       
}

double dir(int i,int j)
{
double a,b,c,aa,bb,cc,yn,xn,d;
int k;
double hmax=0.0,panta,wmax=0.0,panta2;
double xmin,ymin,xmax,ymax;

if(y[i]==y[j])
   {
   for(k=1;k<=nh;k++)
      if((double)modul(y[hull[k]]-y[i])>hmax)
          hmax=(double)modul(y[hull[k]]-y[i]);
         
   xmin=1000005.0;
   xmax=-1.0;
   for(k=1;k<=nh;k++)
      {
      if((double)x[hull[k]]<xmin)
         xmin=(double)x[hull[k]];
      if((double)x[hull[k]]>xmax)
         xmax=(double)x[hull[k]];    
      }
   wmax=xmax-xmin;
   }
else
if(x[i]==x[j])
   {
   for(k=1;k<=nh;k++)
      if((double)modul(x[hull[k]]-x[i])>hmax)
          hmax=(double)modul(x[hull[k]]-x[i]);           
          
   ymin=1000005.0;
   ymax=-1.0;
   for(k=1;k<=nh;k++)
     {
     if((double)y[hull[k]]<ymin)
         ymin=(double)y[hull[k]];
     if((double)y[hull[k]]>ymax)
         ymax=(double)y[hull[k]];
     }
   wmax=ymax-ymin;
   }
else
{
a=(double)y[j]-y[i];
b=(double)x[i]-x[j];
c=(double)x[j]*y[i]-x[i]*y[j];

panta=((double)y[j]-y[i])/(x[j]-x[i]);   
panta2=(-1)/panta;

xmin=ymin=1000005.0;
ymax=xmax=-1.0;

for(k=1;k<=nh;k++)
 {
 aa=panta2;
 bb=-1.0;
 cc=(double)y[hull[k]]-panta2*x[hull[k]];
 
 yn=(aa*c-a*cc)/(a*bb-aa*b);
 xn=((-b)*yn-c)/a;
 
 d=dist(xn,yn,(double)x[hull[k]],(double)y[hull[k]]);
 if(d>hmax)
   hmax=d;
   
 if(xn<xmin)
    {
    xmin=xn;
    ymin=yn;
    }
 if(xn>xmax)
    {
    xmax=xn;
    ymax=yn;
    }
 }
wmax=dist(xmin,ymin,xmax,ymax);
}

return hmax*wmax;       
}


int main()
{
FILE *fin=fopen("rubarba.in","r"),
     *fout=fopen("rubarba.out","w");
int n,i,j,k;    

fscanf(fin,"%d",&n);
for(i=1;i<=n;i++)
  fscanf(fin,"%d%d",&x[i],&y[i]);
  
//sortare pt hull
for(i=1;i<=n;i++)
  {
  j=i;
  while(j/2&&comp(j/2,j)<0)
      {
      intersc(j/2,j);
      j/=2;                     
      }               
  }
  
i=n;
while(i)
 {
 intersc(1,i);       
 i--;
 
 j=1;
 while(1)
  {
  k=2*j;
  if(k>i) break;
  if(k+1<=i&&comp(k+1,k)>0) k++;
  if(comp(k,j)<0) break;
  
  intersc(j,k);
  j=k;         
  }  
 }
 
//hull
nh=2;
hull[1]=1;hull[2]=2;
memset(viz,0,sizeof viz);
viz[1]=viz[2]=1;

for(i=3;i<=n;i++)
  {
  while(nh>=2&&det(hull[nh],hull[nh-1],i)<0)
         {
         viz[hull[nh]]=0;
         nh--;              
         }
  nh++;
  hull[nh]=i;
  viz[i]=1;     
  }
  
for(i=n;i;i--)
  if(viz[i]==0)
    {
    while(nh>=2&&det(hull[nh],hull[nh-1],i)<0)
         {
         viz[hull[nh]]=0;
         nh--;              
         }
    nh++;
    hull[nh]=i;
    viz[i]=1;     
    }

while(det(hull[nh],hull[nh-1],hull[1])<0)
     {
     viz[hull[nh]]=0;
     nh--;                                    
     }

//directia
double sol=dir(hull[nh],hull[1]);
for(i=1;i<nh;i++)
   {
   double v=dir(hull[i],hull[i+1]);
   if(v<sol)
     sol=v;                 
   }
   
fprintf(fout,"%.2f\n",sol);

fclose(fin);
fclose(fout);
return 0;
}