//yy：今天简单入门学了下ORZ

爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。

模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。这就是模拟退火。

题目链接：

1<=n<=10000,-100000<=xi,yi<=100000

题意：找一个点，使得最小

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #define FIRE(x) (x *= 0.98) 8 using namespace std; 9 typedef long long ll;10 const int N = 10005;11 const double inf = 1e17;12 const double PI = acos(-1.0);13 const double eps = 1e-3;14 struct Point{15 double x, y, w;16 Point(){}17 Point(double _x, double _y):x(_x), y(_y) {}18 Point operator -(const Point &b)const{19 return Point(x - b.x,y - b.y);20 }21 double operator *(const Point &b)const{22 return x*b.x + y*b.y;23 }24 }now, ans, po[N];25 double dist(Point a, Point b) { return sqrt((a-b)*(a-b));}26 int n;27 double tot = inf;28 double statistic(Point p) {29 double res = 0.0;30 for(int i = 0; i < n; ++i) res += dist(p, po[i]) * po[i].w;31 if(res < tot) tot = res, ans = p;32 return res;33 }34 double Rand() { return (rand()%1000 + 1) / 1000.0;}35 void SA(double T) {36 double alpha, sub;37 while(T > eps) {38 alpha = 2.0 * PI * Rand();39 Point t(now.x + T * cos(alpha), now.y + T * sin(alpha));40 sub = statistic(now) - statistic(t);41 if(sub >= 0 || exp(sub / T) >= Rand()) now = t;42 FIRE(T);43 }44 T = 0.001;45 for(int i = 1; i <= 1000; ++i) {46 alpha = 2.0 * PI * Rand();47 Point t(ans.x + T * cos(alpha) * Rand(), ans.y + T * sin(alpha) * Rand());48 statistic(t);49 }50 }51 int main(){52 srand(123456);53 scanf("%d", &n);54 for(int i = 0; i < n; ++i) {55 scanf("%lf%lf%lf", &po[i].x, &po[i].y, &po[i].w);56 now.x += po[i].x; now.y += po[i].y;57 }58 now.x /= n; now.y /= n;59 double T = 1000.0;60 SA(T);61 printf("%.3f %.3f\n", ans.x, ans.y);62 return 0;63 }