bzoj3680模拟退火

时间：2023-03-08 22:06:31
bzoj3680模拟退火

看题意就是一道数学物理题，带权费马点   ——这怎么是数学了，这也是物理的

所以要用物理方法，比如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);

 }

相关文章