BZOJ3680 吊打GTY

BZOJ3680 吊打GTY

Link

Description

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

n ≤ 1 0 4 , ∣ X i ∣ , ∣ Y i ∣ ≤ 1 0 5 , 保 留 三 位 小 数 nle10^4,|Xi|,|Yi|le 10^5,保留三位小数 n≤104,∣Xi∣,∣Yi∣≤105,保留三位小数

Solution

也就是要最小化 ∑ i = 1 n w i ∗ d i s i sum_{i=1}^n w_i*dis_i ∑i=1n​wi​∗disi​

物理解法我不多说，这里介绍一下模拟退火。

退火做法是先随便定一个初始坐标。

每次随机将两维坐标分别加上 T ∗ r a n d ( − 1 , 1 ) T*rand(-1,1) T∗rand(−1,1)

然后判断解是否更优，如果更优则直接替换当前解。

否则以 e x p ( ( n o w − a n s ) / T ) exp((now-ans)/T) exp((now−ans)/T)的概率替换当前解

最后在解的附近随机转转，取一个最优的。

为什么退火在这个题上非常靠谱呢？

我们可以思考解的优劣性分布。

发现这个东西呈山谷状，离最优解越远，解越差。

那么退火就会不断向中央走，最终一定会得到最优解。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<ctime>
#define LL long long
using namespace std;
inline int read(){int x=0,f=1;char ch=' ';while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return f==1?x:-x;
}
const int N=1e4+5;
const double eps=1e-3;
inline double Rand(){return (double)rand()/(double)RAND_MAX;
}
int n;
double X[N],Y[N],w[N];
double nowx,nowy,ans=1e18,ansx,ansy;
inline void solve(){double T=1e5;double tmp=1e18;while(T>eps){double x=nowx-T*(Rand()*2-1);double y=nowy-T*(Rand()*2-1);double num=0;for(int i=1;i<=n;++i)num+=w[i]*sqrt((X[i]-x)*(X[i]-x)+(Y[i]-y)*(Y[i]-y));if(num<ans){ans=num;ansx=x;ansy=y;}double c=tmp-num;if(c>0 || exp(c/T)>Rand()){nowx=x;nowy=y;tmp=num;}T*=0.98;}for(int i=1;i<=1000;++i){double x=ansx+eps*(Rand()*2-1);double y=ansy+eps*(Rand()*2-1);double num=0;for(int i=1;i<=n;++i)num+=w[i]*sqrt((X[i]-x)*(X[i]-x)+(Y[i]-y)*(Y[i]-y));if(num<ans){ans=num;ansx=x;ansy=y;}}
}
int main(){srand(time(0));n=read();for(int i=1;i<=n;++i){X[i]=read();Y[i]=read();w[i]=read();nowx+=X[i];nowy+=Y[i];}nowx/=(double)n;nowy/=(double)n;ansx=nowx;ansy=nowy;solve();printf("%.3lf %.3lfn",ansx,ansy);return 0;
}