uva10012 不是那么简单的，有陷阱！

 

首先想的是每次放一个圆形的时候还是先让其与前一个放置的圆相切，然后判断它与再之前放的圆是否相交，如不相交，则说明这样放是正确且最节省距离的，如果有任何一个圆与其相交，则说明不能与前一个圆相切，就再往前推一个，让其与前前个圆相切，再判断是否和别的圆相交。。。为了判断是否相交，增加了一个center数组存储各圆的圆心位置。到此思路很正确很清晰，然后遇到了三个Wa的点。

 

WA1：判断矩形最小size的时候不能用最后一个圆的最右侧位置了，因为有可能最后一个圆很小，其最右侧的位置还不如其前一个圆的最右侧位置远，所以改用判断各圆圆心位置+半径的最大值作为矩形的最小size。

 

WA2：在放置前几个圆的时候注意不能让圆的圆心位置-圆的半径<0。比如说第一个圆半径是1，第二个元半径100，放第二个元就不能让其与第一个圆相切因为那样圆的左边就超出矩形盒子的壁了！

 

WA3：主函数中MinL设置的太小，估计测试数据的数有很大的，题目没有说半径最大是多少，开始设的是65536，结果WA，改成DBL_MAX就AC了！！

 

 

#include<iostream>  #include<cmath>  #include<iomanip>  #include<cstring>  #include<float.h>  using namespace std;    int m,Put[10];          //Put[i]:放置的第i个圆的编号  double MinL,size[10],center[10];//size[i]:编号为i的圆的半径；center[i]:放置的第i个圆的圆心位置  bool vis[10];    double getlen(int a,int b)      //计算两圆心间的距离  {      return sqrt((size[a]+size[b])*(size[a]+size[b])-(size[a]-size[b])*(size[a]-size[b]));  }  bool isok(int a,int b)          //是否和之前放的圆相交  {      for (int i=0;i<b;i++)      {          if (sqrt((center[i]-center[a])*(center[i]-center[a])+(size[Put[i]]-size[Put[a]])*(size[Put[i]]-size[Put[a]]))<(size[Put[i]]+size[Put[a]]))              return false;      }      return true;  }  void dfs(int cur)  {      int i,j;      if (cur==m)      {             double maxsize=0;          for (int k=0;k<cur;k++)          {              if (center[k]+size[Put[k]]>maxsize)                  maxsize=center[k]+size[Put[k]];          }          if (maxsize<MinL)              MinL=maxsize;      }      else      {          for (i=0;i<m;i++)          {              if (!vis[i])              {                  Put[cur]=i;                  vis[i]=1;                  double tmpl;                  bool ok=1;                  for (j=cur-1;j>=0;j--)                  {                      tmpl=getlen(Put[j],i);                      center[cur]=center[j]+tmpl;                      if (center[cur]-size[Put[cur]]<0)                      {ok=0;break;}                      if (isok(cur,j)) break;                  }                  if (ok)                      dfs(cur+1);                  vis[i]=0;              }          }      }  }  int main()  {      int n;      cin>>n;      while(n--)      {          cin>>m;          MinL=DBL_MAX;          memset(vis,0,sizeof(vis));          for (int i=0;i<m;i++)              cin>>size[i];          for (int i=0;i<m;i++)          {              Put[0]=i;              center[0]=size[i];              vis[i]=1;              dfs(1);              vis[i]=0;          }          cout<<fixed<<setprecision(3)<<MinL<<endl;      }      return 0;  }