UVa 10012 - How Big Is It?
题目：给你m个圆，让所有的圆都与底边相切，求一个最小的矩形放下所有圆 。
分析：计算几何、搜索。由于数据较小（8个）所以可以利用搜索枚举所有状态。然后求出其中最小的。
注意：每个圆不一定是与左边相邻的相切，如果用相邻计算可能会覆盖。这里设第一个圆的切点坐标d[1] = (0,0)，然后记录所有切点坐标d[]，每次寻找时枚举所有左边的圆找到相切的，求出对应的与平面的切点。最后没举出最大的d[i]+r[i]和d[i]-r[i]即可。
#include <stdio.h>#include <stdlib.h>#include <math.h>double r[10];int u[10];int m[10];int p[40321][10];int Count;//搜索求全排列 void dfs( int s, int n ) {if ( s > n ) {for ( int i = 1 ; i <= n ; ++ i )p[Count][i] = m[i];Count ++;return;}for ( int i = 1 ; i <= n ; ++ i )if ( !u[i] ) {u[i] = 1;m[s] = i;dfs( s+1, n );u[i] = 0;}}int main(){int n,m;while ( scanf("%d",&n) != EOF ) while ( n -- ) {scanf("%d",&m);double MinL = 0;for ( int i = 1 ; i <= m ; ++ i ) {scanf("%lf",&r[i]);u[i] = 0;MinL += 2.0*r[i];}Count = 0;dfs( 1, m );double a,b,c,d[10];for ( int i = 0 ; i < Count ; ++ i ) {for ( int j = 1 ; j <= m ; ++ j )d[j] = 0;//计算圆与底面切点 for ( int j = 2 ; j <= m ; ++ j ) {for ( int k = 1 ; k < j ; ++ k ) {a = r[p[i][j]]+r[p[i][k]];b = r[p[i][j]]-r[p[i][k]];c = d[k]+sqrt(a*a-b*b);if ( d[j] < c ) d[j] = c;}}//枚举端点找最值 double left = 0,righ = 0;for ( int j = 1 ; j <= m ; ++ j ) {if ( left > d[j]-r[p[i][j]] ) left = d[j]-r[p[i][j]];if ( righ < d[j]+r[p[i][j]] ) righ = d[j]+r[p[i][j]];}if ( MinL > righ-left ) MinL = righ-left;}printf("%.3lf\n",MinL);}return 0;}