看题意就是一道数学物理题,带权费马点 ——这怎么是数学了,这也是物理的
所以要用物理方法,比如FFF
国际著名oi选手miaom曾说
模拟退火初温可以低,但是最好烧个几千次
国际著名物理课代表+1曾说
miaom说什么都对
但是我瞎捣鼓了一波烧了一次不但A了还过了样例(不要说我递进的顺序不对),真是神奇
#include<bits/stdc++.h>
#define MAXN 10000
#define EPS 1e-9
using namespace std;
int wt[MAXN+],n,p,q;
double x,y,ans;
struct point{double x,y;}a[MAXN+],now;
double Rand(){ return 1.0*rand()/RAND_MAX;}
double dist(point a,point b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
double tot(const point p)
{
double sum=;
for(int i=;i<=n;i++)
sum+=dist(p,a[i])*wt[i];
return sum;
}
bool operator<(point a,point b){ return tot(a)<tot(b);}
point min(point a,point b){ return a<b?a:b;}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d%d%d",&p,&q,&wt[i]),a[i]={(double)p,(double)q},x+=p,y+=q;
x/=n,y/=n;
now={x,y};
ans=tot(now);
double T=;
while(T>EPS)
{
double dx=pow(T,2.0/)*(-*Rand()),dy=pow(T,2.0/)*(-*Rand());
point ok={now.x+dx,now.y+dy};
double tr=tot(ok);
double wrong=exp((ans-tr)/T*);
if(wrong>Rand() || tr<ans)
ans=tr,now=ok;
T*=0.99;
}
printf("%.3lf %.3lf\n",now.x,now.y);
}