题链
随即确定一个点，将其他点对该点产生的力正交分解，试能越小越稳定；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include <bits/stdc++.h>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
#define LL long long
#define PI acos(-1.0)
#define eps 1e-8
#define Pair pair<double,double>
#define mod 998244353
#define MAXN 1e18
#define MS 100009
LL n,m;
struct node{
double x,y,w;
}p[MS];
node ans;
double cal(node t){
double cc = 0;
for(int i=1;i<=n;i++){
double dx = p[i].x - t.x;
double dy = p[i].y - t.y;
cc += sqrt(dx*dx+dy*dy)*p[i].w;
}
return cc;
}
void simulate(){
for(double T=3000,r=0.9;T>1e-15;T*=r){
node o;
o.x = ans.x + T*(rand()*2-RAND_MAX);
o.y = ans.y + T*(rand()*2-RAND_MAX);
o.w = cal(o);
double cha = o.w - ans.w;
if(cha < 0){
ans = o;
}
else if(exp(-cha/T)*RAND_MAX>rand()){
ans.x = o.x;
ans.y = o.y;
}
}
}
int main() {
srand(unsigned(time(0)));
cin >> n;
for(int i=1;i<=n;i++){
double x,y,w;
cin >> x >> y >> w;
p[i] = {x,y,w};
ans.x += x;
ans.y += y;
}
ans.x /= n;
ans.y /= n;
ans.w = cal(ans);
LL cnt = 300;
while(cnt--) simulate();
printf("%.3f %.3f\n",ans.x,ans.y);
return 0;
}
|
