JSOI2004 平衡点 / 吊打XXX
题面
分析
正解表示不会
蒟蒻只会用模拟退火
随机一个点,用鬼畜的物理推理得到W=sqrt(dxdx+dydy)*w[i]这个公式,然后评价这个点,再随机,再评价
然后就玄学的A掉了本题
code
#include<bits/stdc++.h>
using namespace std;
#define LD long double
#define RD T*(2*rand()-RAND_MAX)
#define loop(i,start,end) for(int i=start;i<=end;i++)
#define DB double
const int maxn=1010;
DB p_x[maxn],p_y[maxn],w[maxn];
int n;
const LD eps=1e-17;
const LD D=0.99;
LD calc(LD x0,LD y0)
{
LD res=0;
loop(i,1,n)
{
LD nx=x0-p_x[i];LD ny=y0-p_y[i];
res+=sqrt(nx*nx+ny*ny)*w[i];
}
return res;
}
int main()
{
//freopen("datain.txt","r",stdin);
scanf("%d",&n);
LD best,bx=0,by=0;
loop(i,1,n)
{
scanf("%lf%lf%lf",&p_x[i],&p_y[i],&w[i]);
bx+=p_x[i];by+=p_y[i];
}
bx/=n;by/=n;
best=calc(bx,by);
int times=1;
srand(20190129);
while(times--)
{
LD ans=best;LD x_0=bx,y_0=by;
LD x_1,y_1,res;
for(LD T=1000000;T>eps;T*=D)
{
x_1=x_0+RD;
y_1=y_0+RD;
res=calc(x_1,y_1);
if(res<best)
{
best=ans=res;bx=x_0=x_1;by=y_0=y_1;
}
//else if(res>ans&&exp((res-ans)/T)>(LD)rand()/RAND_MAX)
else if(res>ans&&exp((ans-res)/T)>(LD)rand()/RAND_MAX)
{
ans=res;x_0=x_1;y_0=y_1;
}
}
}
printf("%.3Lf %.3Lf",bx,by);
return 0;
}