ImOlivia_uu!

玄学算法，但是有必要知道一下以便日后骗分（）

太幽默了。

洛谷

---

模拟退火

Simulated annealing - Wikipedia

模拟退火算法 - 百度百科

首先这个算法名字就很魔性，还要根据什么固体退火原理，听不懂（bu

其次我们发现这是一个叫做玄学的东西，它的精度会对它的结果和时间复杂度有所影响

思路

使用模拟退火，因为我觉得这就是模拟退火模板题。

代码

#include<bits/stdc++.h>

using namespace std;

struct node
{
	int x,y,w;
} a[10005]; //记录坐标
int n; 

double potential_energy(double nowx,double nowy) //计算势能总和
{
	double sum=0;
	for(int i=1;i<=n;i++)
	{
		double delx=nowx-a[i].x;
		double dely=nowy-a[i].y;
		sum+=(sqrt(delx*delx+dely*dely))*a[i].w;
	}
	return sum;
}

double xans,yans;
double ans=1e18+7,t;
const double delta=0.993; //降温速度

void simulate_anneal()
{
	double xx=xans;
	double yy=yans;
	t=1926; //初始温度，设置成一个比较大的数即可
	while(t>1e-14) //精度
	{
		double xtemp=xans+(rand()*2-RAND_MAX)*t; //随机位置
		double ytemp=yans+(rand()*2-RAND_MAX)*t;
		
		double new_ans=potential_energy(xtemp,ytemp); //势能和与当下最小势能和的差
		double del=new_ans-ans;
		if(del<0) //
		{
			xx=xtemp;
			yy=ytemp;
			xans=xx;
			yans=yy;
			ans=new_ans;
		}
		else if(exp(-del/t)*RAND_MAX>rand()) //exp表示e的x次幂，这里就是求概率
		{
			xx=xtemp;
			yy=ytemp;
		}
		t*=delta; //降温
	}
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y>>a[i].w;
	}
	
	simulate_anneal(); //多跑几遍（
	simulate_anneal();
	simulate_anneal();
	
	printf("%.3lf %.3lf\n",xans,yans);
	
	return 0;
}

---

关于二分

看到 JSOI2004]平衡点 / 吊打XXX - 洛谷专栏 (luogu.com.cn) 这个题解用的是二分，先放在这里吧，回头搞一下咩~