离谱东西
查看原帖
离谱东西
482610
Mortidesperatslav楼主2023/10/14 10:43

照着 OIwiki 写的,交了 41 次没过。

#include<bits/stdc++.h>
using namespace std;
int n,x[1005],y[1005],w[1005];
double ansx,ansy,dis;
double Rand(){
	return(double)rand()/RAND_MAX*2.00-1.00;
}
double ds(double xx,double yy){
	double res=0;
	for(int i=1;i<=n;i++){
		double dx=x[i]-xx,dy=y[i]-yy;
		res+=sqrt(dx*dx+dy*dy)*w[i];
	}
	if (res<dis)dis=res,ansx=xx,ansy=yy;
	return res;
}

void mnth(){
	double t=100000000,nx=ansx,ny=ansy;
	while(t>1e-18){
		double dx=nx+t*Rand(),dy=ny+t*Rand(),delta=ds(dx,dy)-ds(nx,ny);
		if (exp(-delta/t)>(Rand()+1/2.00))nx=dx,ny=dy;
		t*=0.998;
	}
	for(int i=1;i<=1000;i++) {
		double dx=ansx+t*Rand();
		double dy=ansy+t*Rand();
		ds(dx,dy);
	}
}
int main(){
    srand(time(0));
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&x[i],&y[i],&w[i]);
		ansx+=x[i],ansy+=y[i];
	}
	ansx/=n,ansy/=n,dis=ds(ansx,ansy);
    mnth();mnth();mnth();mnth();mnth();mnth();
	printf("%.3lf %.3lf\n",ansx,ansy);
}
2023/10/14 10:43
加载中...