題目：給你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; }
