「Luogu P1337」[JSOI2004]平衡点 / 吊打XXX

发表于 |
字数统计: 353 | 阅读时长 ≈ 2

给定一些带权点，求它们的带权费马点。

链接

Luogu P1337
BZOJ 3680

题解

这题备选的解很多，所以采用猜答案的方法模拟退火来做此题。
注意下一些常数吧……我是不会告诉你我卡了7次的

代码

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll MAXN=1e4+51;
const double delta=0.997;
struct Node{
    double x,y,weight; 
};
Node nd[MAXN];
ll cnt;
double resx,resy,res=1e18,t; 
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline ll randInt()
{
    return 2*rand()-RAND_MAX;
} 
inline double potentialEnergy(double x,double y)
{
    double sum=0,xx,yy;
    for(register int i=0;i<cnt;i++)
    {
        xx=x-nd[i].x,yy=y-nd[i].y;
        sum+=sqrt(xx*xx+yy*yy)*nd[i].weight;
    }	
    return sum;
} 
inline void simulatedAnnealing()
{
    double x=resx,y=resy,rd,xx,yy,dt;
    t=19260;
    while(t>1e-18)
    {
        xx=resx+randInt()*t,yy=resy+randInt()*t;
        rd=potentialEnergy(xx,yy),dt=rd-res;
        if(dt<0)
        {
            x=xx,y=yy,resx=x,resy=y,res=rd;
        }
        else
        {
            if(exp(-dt/t)*RAND_MAX>rand())
            {
                x=xx,y=yy;
            }
        }
        t*=delta; 
    }
}
inline void SA(ll times)
{
    for(register int i=0;i<times;i++)
    {
        simulatedAnnealing();
    }
}
int main()
{
    srand(time(0)); 
    cnt=read();
    for(register int i=0;i<cnt;i++)
    {
        nd[i].x=read(),nd[i].y=read(),nd[i].weight=read();
    }
    SA(9);
    printf("%.3lf %.3lf",resx,resy);
}