題目：動物園有很多休息點，如果動物沖過保護站點間的線段到外面去就會失蹤，現在想建立一個站點是他到休息點的距離和最小，求這個最小的距離和。 分析：計算幾何、凸包、費馬點、隨機。首先，只有凸包的頂點是有意義的休息站；然後，找到到凸包的費馬點即可。這裡使用隨即增量算法逼近求解。由於具有單調性，所以隨機取一個凸包內的點（這裡選擇基准頂點），然後控制步長不斷縮短，在隨機方向上運動不斷逼近到精度滿足即可。 注意：隨機次數的控制，太多會TLE、太少會WA。 [cpp] #include <algorithm> #include <iostream> #include <cstdlib> #include <cstdio> #include <cmath> #include <ctime> using namespace std; typedef struct pnode { double x,y,d; pnode( double a, double b ) {x = a;y = b;} pnode(){}; }point; point Pn,P[105]; double dist( point a, point b ) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double dist( point p, int N ) { double sum = 0.0; for ( int i = 0 ; i <= N ; ++ i ) sum += dist( p, P[i] ); return sum; } double crossproduct( point a, point b, point c ) { return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y); } bool cmp1( point a, point b ) { if ( a.x == b.x ) return a.y < b.y; else return a.x < b.x; } bool cmp2( point a, point b ) { return crossproduct( P[0], a, b ) > 0; } bool cmp3( point a, point b ) { double cp = crossproduct( P[0], a, b ); if ( cp == 0 ) { if ( crossproduct( P[0], a, Pn ) == 0 ) return a.d > b.d; else return a.d < b.d; }else return cp > 0; } double Graham( int N ) { sort( P+0, P+N, cmp1 ); sort( P+1, P+N, cmp2 ); for ( int i = 1 ; i < N ; ++ i ) P[i].d = dist( P[0], P[i] ); Pn = P[N-1]; sort( P+1, P+N, cmp3 ); int top = N; if ( N > 2 ) { top = 2; for ( int i = 3 ; i < N ; ++ i ) { while ( crossproduct( P[top-1], P[top], P[i] ) < 0 ) -- top; P[++ top] = P[i]; } //刪掉共線的點 int now = 1; for ( int i = 2 ; i <= top ; ++ i ) { if ( crossproduct( P[now-1], P[now], P[i] ) == 0 ) P[now] = P[i]; else P[++ now] = P[i]; } top = now; } //隨機增量逼近法 point t,s = P[0]; double sp = 10000.0,esp = 0.01; double temp,min = dist( s, top ); while ( sp > esp ) { int flag = 0; for ( int i = 0 ; i < 10 ; ++ i ) { t = s; int R = rand()%361; t.x += sp*cos(R); t.y += sp*sin(R); temp = dist( t, top ); if ( min > temp ) { min = temp; s = t; flag = 1; } } if ( !flag ) sp /= 2.0; } return min; } int main() { srand( time(NULL) ); int T,N; while ( scanf("%d",&T) != EOF ) while ( T -- ) { scanf("%d",&N); for ( int i = 0 ; i < N ; ++ i ) scanf("%lf%lf",&P[i].x,&P[i].y); printf("%.0lf\n",Graham( N )); if ( T ) printf("\n"); } return 0; }
