2012-05-08 19:34:49Morris
[UVA][Math&DFS] 10012 - How Big Is It?
How Big Is It?
Ian's going to California, and he has to pack his things, including hiscollection of circles. Given a set of circles, your program mustfind the smallest rectangular box in which they fit.All circles must touch the bottom of the box. The figure below showsan acceptable packing for a set of circles (although this may not bethe optimal packing for these particular circles). Note that in anideal packing, each circle should touch at least one other circle(but you probably figured that out).| How Big Is It? |
Input
The first line of input contains a single positive decimal integer n,n<=50. This indicates the number of lines which follow. Thesubsequent n lines each contain a series of numbers separated byspaces. The first number on each of these lines is a positive integerm, m<=8, which indicates how many other numbers appear on thatline. The next m numbers on the line are the radii of the circleswhich must be packed in a single box. These numbers need not beintegers.Output
For each data line of input, excluding the first line of input containingn, your program must output the size of the smallest rectangle which canpack the circles. Each case should be output on a separate line by itself,with three places after the decimal point. Do not output leading zeroesunless 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.65716.00012.657
至少與一個相臨, 且必須貼地
//ANSI C 0.056 s Rank 9
#include <stdio.h>
#include <string.h>
#include <math.h>
double r[10], x[10], map[10][10], ans;
int used[10], rx[10];
void dfs(int idx, int n) {
if(idx == n) {
double xs = 0;
int i;
for(i = 0; i < n; i++)
if(r[rx[i]]+x[i] > xs)
xs = r[rx[i]]+x[i];
if(ans > xs) {
ans = xs;
}
return;
}
int i, j, k, f;
double xs;
for(i = 0; i < n; i++) {
if(!used[i]) {
rx[idx] = i;
f = 0;
xs = r[i];
for(j = idx-1; j >= 0; j--) {
xs = x[j] + 2*map[i][rx[j]];
for(k = j-1; k >= 0; k--) {
if(xs < 2*map[i][rx[k]] + x[k])
break;
}
if(k == -1) {
f = 1;
break;
}
}
if(xs < r[i]) xs = r[i];
x[idx] = xs;
if(f == 0 && idx != 0 || xs + r[i] >= ans)
continue;
used[i] = 1;
dfs(idx+1, n);
used[i] = 0;
}
}
}
int main() {
int n, m, i, j;
scanf("%d", &n);
while(n--) {
scanf("%d", &m);
memset(used, 0, sizeof(used));
ans = 0;
for(i = 0; i < m; i++) {
scanf("%lf", &r[i]);
ans += r[i];
}
for(i = 0; i < m; i++)
for(j = 0; j < m; j++)
map[i][j] = sqrt(r[i]*r[j]);
ans *= 2;
dfs(0, m);
printf("%.3lf\n", ans);
}
return 0;
}