BZOJ3680: 吊打XXX

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int x[1010], y[1010], w[1010];
 4 double ansx, ansy, ans;
 5 inline double R() {
 6     return (double)rand() / RAND_MAX;
 7 }
 8 inline double calc(int n, double xx, double yy) {
 9     double ret = 0; 
10     for(int i = 1; i <= n; ++ i) {
11         double nx = xx - x[i], ny = yy - y[i];
12         ret += (double)sqrt(nx * nx + ny * ny) * w[i];
13     } if(ret < ans) {
14         ans = ret, ansx = xx, ansy = yy;
15     } return ret;
16 }
17 inline void Do(int n) {
18     double tem = 1e5, X = ansx, Y = ansy;
19     while(tem > 1e-4) {
20         double nx = X + tem * (R() - 0.5);
21         double ny = Y + tem * (R() - 0.5);
22         double delta = calc(n, nx, ny) - calc(n, X, Y);
23         if(exp(-delta / tem) > R()) {
24             X = nx, Y = ny;
25         }
26         tem = tem * 0.97;
27     } for(int i = 1; i <= 1000; ++ i) {
28         double nx = ansx + tem * (R() - 0.5);
29         double ny = ansy + tem * (R() - 0.5);
30         calc(n, nx, ny);
31     }
32 }
33 int main() {
34     srand(time(0));
35     int n; scanf("%d",&n);
36     for(int i = 1; i <= n; ++ i) {
37         scanf("%d%d%d", &x[i], &y[i], &w[i]);
38         ansx += x[i], ansy = y[i];
39     } ansx /= n, ansy /= n;
40     ans = calc(n, ansx, ansy);
41     for(int i = 1; i <= 100; ++ i) {
42         Do(n); 
43     }
44     printf("%.3lf %.3lf\n", ansx, ansy);
45 }