[BZOJ3680/Luogu1337]吊打XXX (模拟退火,爬山算法)

发布于 2018-04-06  87 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3680/Luogu1337]吊打XXX (模拟退火,爬山算法)

Description

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

Tag

模拟退火,爬山算法

解决思路

在平面上随机一个点,然后向四周爬山或退火。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

#define ll long long
#define ld double
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=10010;
const int maxM=1;
const ld dt=0.9;
const ld Pi=acos(-1);
const ld eps=1e-4;
const ld inf=1e30;
//const int inf=2147483647;

class Pos
{
public:
    ld x,y;
};

int n;
Pos P[maxN];
ld W[maxN];
Pos Ans[maxN];
ld Dis[maxN];
Pos Outp;
ld ww=inf;

ld Make(ld l,ld r);
ld Calc(Pos P);
ld Dist(Pos A,Pos B);

int main()
{
    //srand(170524^141404);
    ios::sync_with_stdio(false);

    cin>>n;
    ld mxx=-inf,mxy=-inf,mnx=inf,mny=inf;
    for (int i=1;i<=n;i++) cin>>P[i].x>>P[i].y>>W[i];
    ld x0=0,y0=0;
    for (int i=1;i<=n;i++)
    {
        x0+=P[i].x;y0+=P[i].y;
        mxx=max(mxx,P[i].x);mxy=max(mxy,P[i].y);//得到平面范围,方便随机点
        mnx=min(mnx,P[i].x);mny=min(mny,P[i].y);
    }
    x0=x0/n;y0=y0/n;Calc((Pos){x0,y0});//得到中心,先贪心地选择中心
    ld dx=mxx-mnx,dy=mxy-mny;
    Ans[1].x=x0;Ans[1].y=y0;
    Dis[1]=Calc(Ans[1]);
    for (int i=2;i<=maxM;i++)//随机若干个点
    {
        Ans[i].x=x0+Make(-dx*i/maxM,dx*i/maxM)/100;
        Ans[i].y=y0+Make(-dy*i/maxM,dy*i/maxM)/100;
        Dis[i]=Calc(Ans[i]);
    }
    ld T=1000;
    while (T>eps)//开始爬山/退火
    {
        for (int i=1;i<=maxM;i++)
            for (int tim=1;tim<=20;tim++)
            {
                Pos now;
                now.x=Ans[i].x+T*Make(-1.0,1.0);
                now.y=Ans[i].y+T*Make(-1.0,1.0);
                ld d=Dis[i]-Calc(now);
                if ((d>eps)) Ans[i]=now,Dis[i]=Calc(now);
            }
        T=T*dt;
    }
    int id=1;
    for(int tim=1;tim<=1000;tim++)//由于答案最后会在一段区间内,所以要再随机向四周走一走
    {
        Pos now;
        now.x=Ans[id].x+T*Make(-1.0,1.0);
        now.y=Ans[id].y+T*Make(-1.0,1.0);
        ld d=Calc(now);
        if (d<Dis[id]) Ans[id]=now,Dis[id]=d;
    }
    printf("%.3lf %.3lf\n",Outp.x,Outp.y);
    return 0;
}

ld Make(ld l,ld r)
{
    ld dou=(ld)(rand())/RAND_MAX;
    return dou*(r-l)+l;
}

ld Calc(Pos H)
{
    ld sd=0;
    for (int i=1;i<=n;i++)
    {
        ld d=Dist(H,P[i]);
        sd=sd+W[i]*d;
    }
    if (sd<ww) Outp=H,ww=sd;
    return sd;
}

ld Dist(Pos A,Pos B)
{
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3680/Luogu1337]吊打XXX (模拟退火,爬山算法)


HNCJ OIer 一枚