Cod sursa(job #255847)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 10 februarie 2009 19:39:23
Problema Rubarba Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.27 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define Nmax 100005
#define INF 2147000000
#define DD double
using namespace std;
//struct point{int x,y;};
struct kk{DD x,y;}P,P1,P2;
int n,i,j,p,q,H[Nmax],minmax,maxmin,poz,poz1,poz2;
kk a[Nmax]; kk con[Nmax];
DD x1,yy1,x2,y2,x3,y3,x4,y4,x5,y5,xp1,yp1,xp2,yp2,arie,Amin,m12,m34;
DD d,dmax,dm1,dm2,rez;

void intersec(DD x1,DD yy1,DD x2,DD y2,DD x3, DD y3,DD x4,DD y4,DD &X,DD &Y){
 DD A1,A2,B1,B2,C1,C2,det;
 A1=y2-yy1; A2=y4-y3;
 B1=x1-x2; B2=x3-x4;
 C1=A1*x1+B1*yy1;
 C2=A2*x3+B2*y3;
 det=A1*B2-A2*B1;
 if (!det)return ;  
 else{
   X=(DD)(B2*C1-B1*C2)/det;
   Y=(DD)(A1*C2-A2*C1)/det;
  }
}

DD dist(DD x1,DD yy1,DD x2,DD y2,DD x0, DD y0){
  rez=(x0*yy1+y0*x2+x1*y2-x2*yy1-x0*y2-x1*y0)/sqrt((x1-x2)*(x1-x2)+(yy1-y2)*(yy1-y2));
  if (rez<0)rez=-rez;
  return rez;
}
bool cmp (kk P1, kk P2){
  if (P1.x==P2.x)return (P1.y<P2.y);
  else return (P1.x<P2.x);
}
DD isLeft(kk P1, kk P2,kk P){
  return (P2.x-P1.x)*(P.y-P1.y)- (P.x-P1.x)*(P2.y-P1.y);
}
int main(){
  freopen("rubarba.in","r",stdin); freopen("rubarba.out","w",stdout);
  scanf("%d",&n);
  for (i=1;i<=n;++i)scanf("%lf %lf\n",&a[i].x,&a[i].y);
  sort (a+1,a+n+1,cmp);
  //get the min,max and max,min points
  for (i=1; i<=n && a[i].x==a[1].x ;++i);minmax=i-1;
  for (i=n; i && a[i].x==a[n].x ;--i);maxmin=i+1;
  //lower Hull
  p=1; q=0; H[++q]=1;//min,min point...n is the max,max point
  i=minmax;
  while ( ++i <= maxmin ){
   if ( isLeft( a[1] , a[maxmin] , a[i] ) >=0 && i < maxmin ) continue;
   while (q>1){
	 if ( isLeft( a[ H[q-1] ], a[ H[q] ], a[i] ) > 0 ) break;
	 q--;
   }
   H[++q]=i;
  }
  //upper Hull
  if ( maxmin != n ) H[++q] = n;
  p = q;
  i = maxmin;
  while ( --i >= minmax ){
   if ( isLeft( a[n], a[minmax], a[i] ) >= 0 && i > minmax )continue;
   while (q > p){
	if ( isLeft( a[ H[q-1] ], a[ H[q] ], a[i] ) > 0 )break;
	q--;
   }
   H[++q]=i;
  }
  if (minmax==1) q--;
  //construire lista de puncte
  Amin=INF;
  for (i=1;i<=q;++i)con[i]=a[H[i]];
  con[++q]=a[H[1]];
  for (i=1;i<q;++i){
    x1=con[i].x;yy1=con[i].y;
    x2=con[i+1].x;y2=con[i+1].y;
    if (x1!=x2&&yy1!=y2){m12=(y2-yy1)/(x2-x1);m34=-1/m12;}
    else if (x1==x2) m12=INF,m34=0; else m12=0,m34=INF;
    dmax=0;
    for (j=1;j<q;++j){
      d=dist(x1,yy1,x2,y2,con[j].x,con[j].y);
      if (d>dmax){dmax=d;poz=j;}
    }
    x3=con[poz].x;y3=con[poz].y;
    if (m34==INF)x4=x3,y4=5;
    else {x4=5;y4=y3+m34*(x4-x3);}
    P1.x=x3;P1.y=y3; P2.x=x4;P2.y=y4;
    //gasire pct extrem stanga-dreapta
    dm1=0;dm2=0;
    for (j=1;j<=q;++j){
      P.x=con[j].x;P.y=con[j].y;
      if (isLeft(P1,P2,P)<0){d=dist(x3,y3,x4,y4,P.x,P.y);if (d>dm1){dm1=d;poz1=j;}}
      else {d=dist(x3,y3,x4,y4,P.x,P.y);if (d>dm2){dm2=d;poz2=j;}}
    }
    //calculare punct picior perpendiculara
    if (m34==INF)x5=con[poz1].x,y5=5;
    else {x5=5;y5=con[poz1].y+m34*(x5-con[poz1].x);}
    intersec(x1,yy1,x2,y2,x5,y5,con[poz1].x,con[poz1].y,xp1,yp1);
    if (m34==INF)x5=con[poz2].x,y5=5;
    else {x5=5;y5=con[poz2].y+m34*(x5-con[poz2].x);}
    intersec(x1,yy1,x2,y2,x5,y5,con[poz2].x,con[poz2].y,xp2,yp2);
    arie=dmax*sqrt((xp1-xp2)*(xp1-xp2)+(yp1-yp2)*(yp1-yp2));
    if (arie<Amin)Amin=arie;
  }
  printf("%.2lf\n",Amin);
return 0;
}