UVA10012 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. 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 问题链接:UVA10012 How Big Is It? 其中,h=r2-r1,L = sqrt( (r1+r2)^2-(r1-r2)^2) 程序说明:(略) 参考链接:(略) 题记:(略) AC的C++语言程序如下: /* UVA10012 How Big Is It? */ #include <bits/stdc++.h> using namespace std; const int M = 8; double r[M],center[M],res,res2,ans; int m; void search(int k) { if(k != m) { double tmp; res = 0; for(int i = 0; i < k; i++) { tmp = 2 * sqrt(r[i] * r[k]); tmp += center[i]; tmp = max(tmp,r[k]); res = max(res,tmp); } center[k] = res; res2 = max(res2,center[k] + r[k]); search(k + 1); } } void cal() { ans = 1e60; do { res2 = r[0] * 2; center[0] = r[0]; search(1); ans = min(ans,res2); } while(next_permutation(r,r + m)); } int main() { int n; scanf("%d",&n); while(n--) { scanf("%d",&m); for(int i = 0; i < m; i++) scanf("%lf",&r[i]); sort(r,r + m); if(m == 1) ans = r[0] * 2; else cal(); printf("%.3lfn",ans); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |