hdu 2440 Watch out the Animal acm
题目：动物园有很多休息点，如果动物冲过保护站点间的线段到外面去就会失踪，现在想建立一个站点是他到休息点的距离和最小，求这个最小的距离和。
分析：计算几何、凸包、费马点、随机。首先，只有凸包的顶点是有意义的休息站；然后，找到到凸包的费马点即可。这里使用随即增量算法逼近求解。由于具有单调性，所以随机取一个凸包内的点（这里选择基准顶点），然后控制步长不断缩短，在随机方向上运动不断逼近到精度满足即可。
注意：随机次数的控制，太多会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;
}
补充：软件开发 , C++ ,
