首页 > 代码库 > 【BZOJ3680】吊打xxx [模拟退火]

【BZOJ3680】吊打xxx [模拟退火]

2024-09-08 04:03:51   216人阅读

吊打XXX

Time Limit: 10 Sec  Memory Limit: 128 MB
[Submit][Status][Discuss]

Description

　　gty又虐了一场比赛，被虐的蒟蒻们决定吊打gty。
　　gty见大势不好机智的分出了n个分身，但还是被人多势众的蒟蒻抓住了。
　　蒟蒻们将n个gty吊在n根绳子上，每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。
　　吊好gty后蒟蒻们发现由于每个gty重力不同，绳结x在移动。
　　蒟蒻wangxz脑洞大开的决定计算出x最后停留处的坐标，由于他太弱了决定向你求助。
　　不计摩擦，不计能量损失，由于gty足够矮所以不会掉到地上。

Input

　　输入第一行为一个正整数n，表示gty的数目。
　　接下来n行,每行三个整数xi，yi，wi，表示第i个gty的横坐标，纵坐标和重力。
　　对于20%的数据，gty排列成一条直线。

Output

　　输出1行两个浮点数（保留到小数点后3位），表示最终x的横、纵坐标。

Sample Input

　　3
　　0 0 1
　　0 2 1
　　1 1 1

Sample Output

　　0.577 1.000

HINT

　　对于50%的数据，1<=n<=1000。
　　对于100%的数据，1<=n<=10000,-100000<=xi,yi<=100000

Main idea

　　求一个坐标，使得整个坐标到其余点的dist*val最小。

Source

　　我们看到这种数据，显然使用模拟退火即可。

Code

技术分享
 1 #include<iostream>   2 #include<algorithm>   3 #include<cstdio>   4 #include<cstring>   5 #include<cstdlib>   6 #include<cmath>   7 using namespace std; 8 typedef long long s64; 9  10 const int ONE = 10005;11 const int INF = 2147483640;12 13 int n;14 double Ans_min = 1.0*1e18;15 double T;16 17 struct power18 {19         double x,y;20         double val;21 }a[ONE],Now,Ans,A;22 23 int get()24 {25         int res=1,Q=1;    char c;26         while( (c=getchar())<48 || c>57)27         if(c==‘-‘)Q=-1;28         if(Q) res=c-48; 29         while((c=getchar())>=48 && c<=57) 30         res=res*10+c-48; 31         return res*Q; 32 }33 34 double dist(power a,power b)35 {36         return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );37 }38 39 double Judge(power Now)40 {41         double res=0;42         for(int i=1;i<=n;i++)43             res+= a[i].val * dist(Now,a[i]);44         if(res < Ans_min) Ans_min = res, Ans = Now; 45         return res;46 }47 48 double Random() {return (double)rand()/RAND_MAX;}49 void SA(double T)50 {51         Now = Ans;52         while(T > 0.001)53         {54             A.x = Now.x + T*(Random() * 2 -1);55             A.y = Now.y + T*(Random() * 2 -1);56             double dE = Judge(Now) - Judge(A);57             if(dE > 0 || exp(dE/T)>Random())58                 Now = A;59             T *= 0.98;60         }61         for(int i=1; i<=1000; i++)62         {63             A.x = Ans.x + T*(Random() * 2 - 1);64             A.y = Ans.y + T*(Random() * 2 - 1);65             Judge(A);66         }67 }68 69 int main()70 {71         n=get();72         for(int i=1;i<=n;i++)73         {74             a[i].x=get();    a[i].y=get();    a[i].val=get();75             Ans.x += a[i].x;    Ans.y += a[i].y;76         }77         Ans.x/=n;    Ans.y/=n;78     79         SA(1000001);80         81         printf("%.3lf %.3lf",Ans.x,Ans.y);82 }
View Code

 

【BZOJ3680】吊打xxx [模拟退火]


联系
我们