吊打XXX bzoj-3680
题目大意：在平面上给定n个点，每个点有一个权值。请在平面上找出一个点（不一定在这n个点内找）使得这个点到n个点的距离*权值最小，即求这n个点的重心。
注释：$1\le n\le 10^4$，$-10^5\le x_i,y_i\le 10^5$。
想法：
模拟退火裸题。
身为一个随机化算法，模拟退火在时间允许的情况下是完全由于爬山的。模拟退火，说白了就是有一定的接受差解的概率，而爬山算法不会接受错解。换言之，爬山是模拟退火的一种极端情况。
模拟物理的降温，就是模拟退火的精髓，不在赘述。
最后，附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define N 10010
double minans=23333333333333333ll;
using namespace std;
int n;
struct Node
{
double x,y,g;
}a[N],ans;
inline double dis(const Node &x,const Node &y)
{
return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
double Judge(const Node &p)
{
double re=0;
for(int i=1;i<=n;i++)
{
re+=a[i].g*dis(p,a[i]);
}
if(re<minans) ans=p,minans=re;
return re;
}
double Rand()
{
return 1.0*rand()/RAND_MAX;
}
void Simulate_Anneal(double T)
{
Node Now=ans;
while(T>0.001)
{
Node Neo;
Neo.x=Now.x+T*(Rand()*2-1);
Neo.y=Now.y+T*(Rand()*2-1);
double dlt=Judge(Now)-Judge(Neo);
if(dlt>0 || exp(dlt/T)>Rand() ) Now=Neo;
T*=0.99;
}
for(int i=1;i<=100;i++)
{
Node Neo;
Neo.x=ans.x+T*(Rand()*2-1);
Neo.y=ans.y+T*(Rand()*2-1);
Judge(Neo);
}
}
int main()
{
srand(19260817);//万里长城永不倒，我为长者续一秒
cin >> n ;
for(int i=1;i<=n;i++)
{
scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].g);
ans.x+=a[i].x,ans.y+=a[i].y;
}
ans.x/=n,ans.y/=n;
Simulate_Anneal(10000);
printf("%.3lf %.3lf\n",ans.x,ans.y);
return 0;
}
小结：模拟退火其实是很强的，但是作为一个OIer能不用还是不用了吧... ...