BZOJ 3680: 吊打XXX （模拟退火）

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

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

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

题目链接：BZOJ 3680: 吊打XXX

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

题意：找一个点

，使得

最小

1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <climits>
 6 #include <cstdlib>
 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 }      

View Code

转载于:https://www.cnblogs.com/GraceSkyer/p/7247532.html