zoj 2928 Mathematical contest in modeling( 爬山 )

看着超哥的代码打的...

觉得爬山和退火算法挺神奇的，这都能搞出结果了

题意：给出三维空间n个点，求出到这n个点的距离之和最小的一个点

虽然不知道为什么是单峰的，但是想想还是觉得有道理

设s(i)为状态i到所有点的距离

爬山就是应付单峰函数的，从状态x开始爬，假设爬到y，如果s(y)<s(x)，就把当前状态更新为y

枚举完一个点所能到的所有点，再缩小爬的距离

http://www.cnblogs.com/heaad/archive/2010/12/20/1911614.html

这里讲的真心好

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<cstdlib>
#include<stack>
using namespace std;

#define inf 0x3f3f3f3f
#define eps 1e-8
#define LL long long
#define ULL unsigned long long
#define MP make_pair
#define pb push_back
#define ls i << 1
#define rs ls | 1
#define md ( ( ll[i] + rr[i] ) >> 1 )
#define mxn 100020

struct point {
 double x, y, z;
 point() {}
 point( double x, double y, double z ): x( x ), y( y ), z( z ) {}
 void input() {
  scanf( "%lf%lf%lf", &x, &y, &z );
 }
 point operator - ( const point &b ) const {
  return point( x - b.x, y - b.y, z - b.z );
 }
 double len() {
  return sqrt( x * x + y * y + z * z );
 }
}p[mxn];

int n;
int dx[30], dy[30], dz[30];
int tot = 0;

double calc( point cur ) {
 double ret = 0;
 for( int i = 0; i < n; ++i ) 
  ret += ( p[i] - cur ).len();
 return ret;
}
void solve() {
 point cur = point( 0, 0, 0 );
 double dlt = 0;
 for( int i = 0; i < n; ++i )
  dlt = max( dlt, ( p[i] - cur ).len() );
 while( dlt > eps ) {   // 每次爬的距离
  point pre = cur;
  double k = calc( cur );
  for( int i = 0; i < tot; ++i ) {  // 枚举爬的各个方向
   point nxt = point( pre.x + dx[i] * dlt, pre.y + dy[i] * dlt, pre.z + dz[i] * dlt );
   double kk = calc( nxt );
   if( kk < k ) { //到达新的状态的总距离比当前的总距离小
    cur = nxt;
    k = kk;
   }
  }
  dlt *= 0.992; // 缩小爬的距离
 }
 printf( "%.3lf %.3lf %.3lf\n", cur.x, cur.y, cur.z );
}
int main() {
 for( int i = -1; i <= 1; ++i )
  for( int j = -1; j <= 1; ++j )
   for( int k = -1; k <= 1; ++k ) 
    dx[tot] = i, dy[tot] = j, dz[tot++] = k;
 while( scanf( "%d", &n ) != EOF ) {
  for( int i = 0; i < n; ++i )
   p[i].input();
  solve();
 }
 return 0;
}