模拟退火 P5544题解

Prean · 2020-08-08 23:54:41 · 题解

题目大意

题意这么明显就不说了qwq

首先最值，而且也想不到啥解法，果断 \rm SA 。

然后是初始位置。初始位置就是 ((\sum_{i=1}^m x)/m,(\sum_{i=1}^m y)/m) 。

然后多跑几遍 \rm SA 就行了qwq。本人跑了55遍，提交过100多遍，虽然说Ynoi比这个还要狠。

code：

#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("Ofast")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
typedef double db;
const db delta=0.99;
db x,y;
struct Node{
    int x,y,r;
}a[15],w[1005];
int n,m,k,r,ans;
inline db p(const db x){
    return x*x;
}
inline db DIS(db x,db y,db a,db b){
    return sqrt(p(x-a)+p(y-b));
}
int calc_energy(const register db x,const register db y){
    register int i,ans=0;
    register db Dis=r;
    for(i=1;i<=n;++i){
        db dis=DIS(a[i].x,a[i].y,x,y)-a[i].r;
        if(dis<0)return 0;
        if(Dis>dis)Dis=dis;
    }
    for(i=1;i<=m;++i)if(DIS(w[i].x,w[i].y,x,y)<=Dis)++ans;
    return ans;
}
void simulate_anneal(){
    db ax=x,ay=y;
    for(register db t=3000;t>1e-16;t*=delta){
        db X=x+((rand()<<1)-RAND_MAX)*t,Y=y+((rand()<<1)-RAND_MAX)*t;
        db now=calc_energy(X,Y);db Delta=ans-now;
        if(Delta<0)x=ax=X,y=ay=Y,ans=now;
        if(exp(-Delta/t)<rand())ax=X,ay=Y;
    }
}
signed main(void){
    srand(time(NULL));
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);std::cout.tie(0);
    int i;
    std::cin>>n>>m>>r;
    for(i=1;i<=n;++i){
        std::cin>>a[i].x>>a[i].y>>a[i].r;
    }
    for(i=1;i<=m;++i){
        std::cin>>w[i].x>>w[i].y;
        x+=w[i].x;y+=w[i].y;
    }
    x/=m;y/=m;
    for(i=1;i<=55;++i)simulate_anneal();
    std::cout<<ans;
}