UVa 10012 - How Big Is It?
题目：给你m个圆，让所有的圆都与底边相切，求一个最小的矩形放下所有圆 。
分析：计算几何、搜索。由于数据较小（8个）所以可以利用搜索枚举所有状态。然后求出其中最小的。
注意：每个圆不一定是与左边相邻的相切，如果用相邻计算可能会覆盖。这里设第一个圆的切点坐标d[1] = (0,0)，然后记录所有切点坐标d[]，每次寻找时枚举所有左边的圆找到相切的，求出对应的与平面的切点。最后没举出最大的d[i]+r[i]和d[i]-r[i]即可。
[cpp]
#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;
}
补充：软件开发 , C++ ,
