3680: 吊打XXX
Time Limit: 10 Sec Memory Limit: 128 MBSec Special JudgeSubmit: 3192 Solved: 1198
[Submit][Status][Discuss]
Description
gty又虐了一场比赛，被虐的蒟蒻们决定吊打gty。gty见大势不好机智的分出了n个分身，但还是被人多势众的蒟蒻抓住了。蒟蒻们将
n个gty吊在n根绳子上，每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。吊好gty后蒟蒻们发现由于每个gty重力不同，绳
结x在移动。蒟蒻wangxz脑洞大开的决定计算出x最后停留处的坐标，由于他太弱了决定向你求助。
不计摩擦，不计能量损失，由于gty足够矮所以不会掉到地上。
Input
输入第一行为一个正整数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
Output
输出1行两个浮点数（保留到小数点后3位），表示最终x的横、纵坐标。
Sample Input
0 0 1
0 2 1
1 1 1
Sample Output
HINT
Source
题目链接：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 }
