当前位置：首页 > news >正文

[BZOJ 3680]吊打XXX（模拟退火）

news 来源：原创 2024/4/20 21:34:53

Description

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

Solution

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

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

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

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#define MAXN 10005
using 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<t)t=res,ansmin_x=xx,ansmin_y=yy;
    return res;
}
int main()
{
    srand(299792458);
    n=read();
    for(int i=1;i<=n;i++)
    x[i]=read(),y[i]=read(),w[i]=read(),ansx+=x[i],ansy+=y[i];
    ansx/=n,ansy/=n;
    ansmin_x=ansx,ansmin_y=ansy,t=judge(ansx,ansy);
    double T=1e6,r=0.99;
    while(T>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;
}