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

发布时间：2015-05-27 19:24:23作者：知识屋

这道题第一次做以为是一般的回溯题，最初的思路就是将各圆形全排列，放置新圆的时候让其与前一个圆相切，最后通过回溯得到矩形的最小size。十几分钟编完后结果WA，想了好一会发现问题所在，不能只让其与前一个圆相切（如果第一个圆很大，半径比方说是100，第二个圆很小，半径是1，第三个圆也很大，半径同样是100，放第三个圆的时候如果是和第二个圆相切则必定会与第一个圆相交，就不可以了）。然后就开始修改代码，然后就遇到了各种错误，断断续续地弄了一晚上加一上午。

首先想的是每次放一个圆形的时候还是先让其与前一个放置的圆相切，然后判断它与再之前放的圆是否相交，如不相交，则说明这样放是正确且最节省距离的，如果有任何一个圆与其相交，则说明不能与前一个圆相切，就再往前推一个，让其与前前个圆相切，再判断是否和别的圆相交。。。为了判断是否相交，增加了一个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;  }

（免责声明：文章内容如涉及作品内容、版权和其它问题，请及时与我们联系，我们将在第一时间删除内容，文章内容仅供参考）