uva10012 How Big Is It?

有点小坑的一道题。。一开始没多想就写了全排列看相邻两个球。。但是可能会有两个极大的圆。。。

用坐标来确定每一个球的点。。枚举当前点和之前已经确定了圆相切后确定最右边的坐标，最后确定RECT最大值。

题目：

How Big Is It?

Ian's going to California, and he has to pack his things, including his collection of circles. Given a set of circles, your program must find the smallest rectangular box in which they fit. All circles must touch the bottom of the box. The figure below shows an acceptable packing for a set of circles (although this may not be the optimal packing for these particular circles). Note that in an ideal packing, each circle should touch at least one other circle (but you probably figured that out).

Input

The first line of input contains a single positive decimal integer n, n<=50. This indicates the number of lines which follow. The subsequent n lines each contain a series of numbers separated by spaces. The first number on each of these lines is a positive integer m, m<=8, which indicates how many other numbers appear on that line. The next m numbers on the line are the radii of the circles which must be packed in a single box. These numbers need not be integers.

Output

For each data line of input, excluding the first line of input containing n, your program must output the size of the smallest rectangle which can pack the circles. Each case should be output on a separate line by itself, with three places after the decimal point. Do not output leading zeroes unless the number is less than 1, e.g. 0.543.

Sample Input

3
3 2.0 1.0 2.0
4 2.0 2.0 2.0 2.0
3 2.0 1.0 4.0

Sample Output

9.657
16.000
12.657


代码：

 1 #include <iostream>
 2 #include <memory.h>
 3 #include <cmath>
 4 #include <cstdlib>
 5 #include <cstdio>
 6 #include <algorithm>
 7 using namespace std;
 8 
 9 double rad[10];
10 int vis[10];
11 int n;
12 double MIN=0;
13 double X[10];
14 double num[10];
15 
16 
17 double findmax ( int u,int last)
18 {
19     double x=rad[u];
20     for(int i=0;i<last;i++)
21     {
22         x= max (x, sqrt(  pow(rad[u]+num[i],2)-pow(num[i]-rad[u],2)  )+X[i]);
23       //   cout<<"X: "<<x<<endl;
24     }
25     return x;
26 }
27 
28 void dfs(int cur)
29 {
30     if(cur==n){
31             double l  = num[0];
32             double ans = X[n-1] + num[n-1];
33             for(int i=0;i<n-1;i++)
34             {
35                 if( X[i]+num[i] > ans) ans = X[i] +num[i];
36             }
37             for(int i=1;i<n;i++)
38             {
39                 if(num[i]-X[i]>l)  l= num[i]-X[i];　　　　　　//因为第一个圆心为零点， l代表左边超出的部分
40             }
41             ans += l;
42 
43             if(ans<MIN)MIN=ans;
44 
45             return ;
46     }
47         for(int i=0;i<n;i++)
48         {
49             if(!vis[i])
50             {
51                 X[cur] = findmax(i,cur);
52                 //cout<<"Cur : "<<cur<<"  "<<X[cur]<<endl;
53                 num[cur] = rad[i];
54                 vis[i]=1;
55                 dfs(cur+1);
56                 vis[i]=0;
57             }
58         }
59 }
60 
61 int main()
62 {
63     int tst;
64     cin>>tst;
65     while(tst--)
66     {
67 
68         cin>>n;
69         MIN=0x7FFFFFFF;
70         for(int i=0;i<n;i++)
71         {
72             cin>>rad[i];
73         }
74         for(int i=0;i<n;i++)
75         {
76             vis[i]=1;
77             X[0]=0;num[0]=rad[i];
78             dfs(1);
79             vis[i]=0;
80         }
81        printf("%.3lf
",MIN);
82     }
83 
84 
85     return 0;
86 
87 }