Time Limit: 10 Sec Memory Limit: 128 MBSec Special Judge
Submit: 3192 Solved: 1198
gty又虐了一场比赛,被虐的蒟蒻们决定吊打gty。gty见大势不好机智的分出了n个分身,但还是被人多势众的蒟蒻抓住了。蒟蒻们将 n个gty吊在n根绳子上,每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。吊好gty后蒟蒻们发现由于每个gty重力不同,绳 结x在移动。蒟蒻wangxz脑洞大开的决定计算出x最后停留处的坐标,由于他太弱了决定向你求助。 不计摩擦,不计能量损失,由于gty足够矮所以不会掉到地上。
输入第一行为一个正整数n(1<=n<=10000),表示gty的数目。 接下来n行,每行三个整数xi,yi,wi,表示第i个gty的横坐标,纵坐标和重力。 对于20%的数据,gty排列成一条直线。 对于50%的数据,1<=n<=1000。 对于100%的数据,1<=n<=10000,-100000<=xi,yi<=100000
输出1行两个浮点数(保留到小数点后3位),表示最终x的横、纵坐标。
3 0 0 1 0 2 1 1 1 1
0.577 1.000
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3680
分析:我反正是被坑死啦,这题谁跟我说是水题的,!!!!!模拟退火算法-----高级,爬山算法------今天才听说过QAQ,好的吧,学习一下,毕竟是道裸题~~~
题目大意:给定n个质点,求重心,这n个质点的重心满足Σ(重心到点i的距离)*g[i]最小,模拟退火的裸题,这题INF开0x3f妥妥过不去。。。起码要max_of _long_long附近才可以!
思路:puts("nan nan");得AC//BZOJ貌似是这个样子的呢,很多题这样写都会AC
爬山就够了,模拟退火也可以。
模拟退火就是在模拟一个退火的过程,他和爬山的区别就在于,它多了一个温度参数。
我们可以发现,越到后面,我们就越接近。所以我们应该把修改的范围越改越小,接受较劣解的可能性也应该调小。
于是我们引入一个温度变量T,膜你退火的过程,温度逐渐下降。
下面给出模拟退火的流程:
设定初始较高的温度T
while 温度>设定的最低值
随机得到一个新解(温度越高,新解与旧解的差异越大)
更新答案
根据新解与旧解之间的优劣关系,以一定概率接受新解(越优越有可能)
以一定方式降温
endwhile
为了保证答案的质量,我们可以在最优解附近再进行随机,并更新答案
模拟退火代码如下:【代码跑的很慢很慢。10000ms+】
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int M=10010;
4 struct Node
5 {
6 double x,y,g;
7 }point[M],ans;
8 int n;
9 double minans=1e100;
10 inline double dis(const Node &a,const Node &b)
11 {
12 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
13 }
14 inline double judge(const Node &p)
15 {
16 int i;
17 double re=0;
18 for(i=1;i<=n;i++)
19 {
20 re+=point[i].g*dis(p,point[i]);
21 }
22 if(re<minans)
23 {
24 ans=p;
25 minans=re;
26 }
27 return re;
28 }
29 inline double Rand()
30 {
31 return rand()%1000/1000.0;
32 }
33 inline void SA(double T)
34 {
35 int i;
36 Node now=ans;
37 while(T>0.001)
38 {
39 Node Neo;
40 Neo.x=now.x+T*(Rand()*2-1);
41 Neo.y=now.y+T*(Rand()*2-1);
42 double de=judge(now)-judge(Neo);
43 if(de>0||exp(de/T)>Rand())
44 now=Neo;
45 T*=0.993;
46 }
47 for(i=1;i<=1000;i++)
48 {
49 Node Neo;
50 Neo.x=ans.x+T*(Rand()*2-1);
51 Neo.y=ans.y+T*(Rand()*2-1);
52 judge(Neo);
53 }
54 }
55 int main()
56 {
57 int i;
58 srand(19980805);
59 cin>>n;
60 for(i=1;i<=n;i++)
61 {
62 scanf("%lf%lf%lf",&point[i].x,&point[i].y,&point[i].g);
63 ans.x+=point[i].x;
64 ans.y+=point[i].y;
65 }
66 ans.x/=n;
67 ans.y/=n;
68 SA(1000000);
69 printf("%.3lf %.3lf\n",ans.x,ans.y);
70 return 0;
71 }
爬山算法代码如下【快了8000ms+】
1 #include <bits/stdc++.h>
2 using namespace std;
3 int n;
4 double ansx,ansy;
5 struct data
6 {
7 double x,y;
8 int w;
9 }p[10005];
10 inline double sqr(double x)
11 {
12 return x*x;
13 }
14 inline double dis(double x,double y,data p)
15 {
16 return sqrt(sqr(x-p.x)+sqr(y-p.y));
17 }
18 void hillclimb()
19 {
20 double t=1000,x,y;
21 for(int i=1;i<=n;i++)
22 ansx+=p[i].x*p[i].w,ansy+=p[i].y*p[i].w;
23 ansx/=n;
24 ansy/=n;
25 while(t>0.00000001)
26 {
27 x=y=0;
28 for(int i=1;i<=n;i++)
29 {
30 x+=(p[i].x-ansx)*p[i].w/dis(ansx,ansy,p[i]);
31 y+=(p[i].y-ansy)*p[i].w/dis(ansx,ansy,p[i]);
32 }
33 ansx+=x*t;ansy+=y*t;
34 if(t>0.5)t*=0.5;
35 else t*=0.97;
36 }
37 printf("%.3lf %.3lf",ansx,ansy);
38 }
39 int main()
40 {
41 scanf("%d",&n);
42 for(int i=1;i<=n;i++)
43 scanf("%lf%lf%d",&p[i].x,&p[i].y,&p[i].w);
44 hillclimb();
45 return 0;
46 }