Description

gty又虐了一場(chǎng)比賽，被虐的蒟蒻們決定吊打gty。gty見大勢(shì)不好機(jī)智的分出了n個(gè)分身，但還是被人多勢(shì)眾的蒟蒻抓住了。蒟蒻們將
n個(gè)gty吊在n根繩子上，每根繩子穿過天臺(tái)的一個(gè)洞。這n根繩子有一個(gè)公共的繩結(jié)x。吊好gty后蒟蒻們發(fā)現(xiàn)由于每個(gè)gty重力不同，繩
結(jié)x在移動(dòng)。蒟蒻wangxz腦洞大開的決定計(jì)算出x最后停留處的坐標(biāo)，由于他太弱了決定向你求助。
不計(jì)摩擦，不計(jì)能量損失，由于gty足夠矮所以不會(huì)掉到地上。

Input

輸入第一行為一個(gè)正整數(shù)n(1<=n<=10000)，表示gty的數(shù)目。
接下來n行,每行三個(gè)整數(shù)xi，yi，wi，表示第i個(gè)gty的橫坐標(biāo)，縱坐標(biāo)和重力。
對(duì)于20%的數(shù)據(jù)，gty排列成一條直線。
對(duì)于50%的數(shù)據(jù)，1<=n<=1000。
對(duì)于100%的數(shù)據(jù)，1<=n<=10000,-100000<=xi,yi<=100000

Output

輸出1行兩個(gè)浮點(diǎn)數(shù)（保留到小數(shù)點(diǎn)后3位），表示最終x的橫、縱坐標(biāo)。

Sample Input

3
0 0 1
0 2 1
1 1 1

Sample Output

0.577 1.000

HINT

?

思路： 這個(gè)題目是我是用模擬題退火做的，模擬退火是一個(gè)很神奇的概率算法，關(guān)鍵是調(diào)參數(shù)和精度誤差。

主要的思路：?

膜你退火就是在膜你一個(gè)退火的過程，他和爬山的區(qū)別就在于，它多了一個(gè)溫度參數(shù)。

我們可以發(fā)現(xiàn)，越到后面，我們就越接近。

所以我們應(yīng)該把修改的范圍越改越小，接受較劣解的可能性也應(yīng)該調(diào)小。

于是我們引入一個(gè)溫度變量T，膜你退火的過程，溫度逐漸下降。

下面給出模擬退火的流程：

設(shè)定初始較高的溫度T

????? while 溫度>設(shè)定的最低值

???????? 隨機(jī)得到一個(gè)新解（溫度越高，新解與舊解的差異越大）

???????? 更新答案

???????? 根據(jù)新解與舊解之間的優(yōu)劣關(guān)系，以一定概率接受新解（越優(yōu)越有可能）

???????? 以一定方式降溫

????? endwhile

為了保證答案的質(zhì)量，我們可以在最優(yōu)解附近再進(jìn)行隨機(jī)，并更新答案

?

1 #include<bits/stdc++.h> 2 using namespace std; 3 #define RD T*(2*rand()-RAND_MAX) 4 #define gc() getchar() 5 #define R register int 6 #define rep(i,a,b) for(R i=a;i<=b;i++) 7 #define Rep(i,a,b) for(R i=a;i>=b;i--) 8 9 int const N=1000+3; 10 long double const D=0.97; 11 long double const eps=1e-14; 12 long double x[N],y[N],w[N]; 13 int n; 14 15 template<class T>void read(T &x){ 16 x=0; char c=0; int w=0; 17 while (!isdigit(c)) w|=c=='-',c=gc(); 18 while (isdigit(c)) x=x*10+(c^48),c=gc(); 19 if(w) x=-x; 20 } 21 long double calc(long double vx,long double vy){ 22 long double ret=0; 23 rep(i,1,n) { 24 long double dx=vx-x[i]; 25 long double dy=vy-y[i]; 26 long double t=sqrt(dx*dx+dy*dy); 27 ret+=t*w[i]; 28 } 29 return ret; 30 } 31 int main(){ 32 long double T,x0,y0,x1,y1,res,ans,best,bx=0,by=0; 33 read(n); 34 rep(i,1,n){ 35 read(x[i]),read(y[i]),read(w[i]); 36 bx+=x[i]; by+=y[i]; 37 } 38 srand(time(0)); 39 bx/=n;by/=n; 40 best=ans=calc(bx,by); 41 int sum=1; 42 while (sum--){ 43 x0=bx;y0=by; ans=best; 44 for (T =100000; T>eps;T*=D){ 45 x1=x0+RD; y1=y0+RD; 46 long double tmp=calc(x1,y1); 47 if(best>tmp) best=tmp,bx=x1,by=y1; 48 if(ans>tmp || exp((ans-tmp)/T)>(long double)rand()/RAND_MAX) 49 ans=tmp,x0=x1,y0=y1; 50 } 51 } 52 printf("%0.3Lf %0.3Lf\n",bx,by); 53 return 0; 54 } View Code

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/ZJXXCN/p/10248003.html

總結(jié)

以上是生活随笔為你收集整理的bzoj 3680 吊打xxx的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。