3301.cpp

北大ACM3301题 德州旅行问题

#include<stdio.h>
#include<math.h>
#include<assert.h>
#define N 1000
#define M_PI 3.14159265358
double x[100],y[100],xx,yy,base,scale,minx,maxx,miny,maxy,dx,dy,dd,best;
int rep,n,i,j,k,T,besti;

void input()
{
 for(i=0;i<n;i++) 
		  scanf("%lf%lf",&x[i],&y[i]);//输入每点的XY值
      best=1000;
      base=0;
}
void make()
{
 for(i=0;i<N;i++)
 {
  double sininc=sin(base+scale*i*M_PI/2/N);//旋转
  double cosinc=cos(base+scale*i*M_PI/2/N);//旋转
  maxx=maxy=-1e99;
  minx=miny=1e99;
  for(j=0;j<n;j++)
			{
               xx=cosinc*x[j]-sininc*y[j];
               yy=sininc*x[j]+cosinc*y[j];
               
               if(xx<minx)minx=xx;
               if(xx>maxx)maxx=xx;
               if(yy<miny)miny=yy;
               if(yy>maxy)maxy=yy;
            }//求出四个端点
            dx=maxx-minx;
            dy=maxy-miny;
            dd=dx;
            if(dy>dd)
				dd=dy;
            if(dd<best)
			{
               best=dd;
               besti=i;
            }
 }        
}



int main()
{
   
   scanf("%d\n",&T);//输入T
   for(T;T>0;T--)
   {
      assert(1==scanf("%d",&n));//输入n
	  input();
      best=1000;
      base=0;
	  scale=1;
	  make();
      base+=scale*(besti-1)*M_PI/2/N;
      scale=scale/N*2;
      printf("%0.2lf\n",best*best);

   }
   return 0;
   
}