Description

gty又虐了一场比赛，被虐的蒟蒻们决定吊打gty。gty见大势不好机智的分出了n个分身，但还是被人多势众的蒟蒻抓住了。蒟蒻们将n个gty吊在n根绳子上，每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。吊好gty后蒟蒻们发现由于每个gty重力不同，绳结x在移动。蒟蒻wangxz脑洞大开的决定计算出x最后停留处的坐标，由于他太弱了决定向你求助。不计摩擦，不计能量损失，由于gty足够矮所以不会掉到地上。

Solution

题面丧病…似乎是一道模拟退火的板子题，求的那个东西叫做广义费马点

从昨天晚上WA到今天，各种调参数

呜呜呜RP太差了…AC率又不知道掉到哪里去了…再也不玩什么随机化算法了…

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define MAXN 10005using namespace std;int n;int x[MAXN],y[MAXN],w[MAXN];double ansmin_x,ansmin_y,t;double ansx=0,ansy=0;inline double read(){ int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}inline double Random(){ return (double)(rand()%10000)/10000.0;}inline double dis(double x1,double y1,double x2,double y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}double judge(double xx,double yy){ double res=0; for(int i=1;i<=n;i++) res+=dis(xx,yy,x[i],y[i])*w[i]; if(res
           
            1e-3) { double xx,yy; xx=ansx+T*(Random()*2-1.0); yy=ansy+T*(Random()*2-1.0); double dE=judge(ansx,ansy)-judge(xx,yy); if(dE>0||exp(dE/T)>Random())ansx=xx,ansy=yy; T*=r; } for(int i=1;i<=1000;i++) { double xx=ansmin_x+(Random()*2-1.0)*T,yy=ansmin_y+(Random()*2-1.0)*T; judge(xx,yy); } printf("%.3lf %.3lf\n",ansmin_x,ansmin_y); return 0;}