题解 P5544 【[JSOI2016]炸弹攻击1】
恶臭玄学AC紫题模拟退火祭
这还是一道朴素模拟退火，推荐和我一样刚入门的新手做。
主体还是和其他题目差不多的模拟退火模板，精髓还是计算函数的部分。
计算函数部分主要思路：
首先，我们已知此时需要计算的点。
其次，枚举所有建筑并求出建筑中心到炸弹的距离。注意，此处计算完距离之后需要再减去建筑的半径
然后对比求出此段距离与目前最优或者极限值，取较小的一个。（因为如果取了较大的会导致更近的建筑受损。）
计算距离的话，咱都是做紫题的人了，不可能不会吧？
当然，不要忘记变量类型是 double ！
（作者因为类型打成 int 卡了半天）
模拟退火的部分也有需要注意的点：
这次求的是最大值，所以记得是
最后就是玄学调参，并没有什么好说的，总之就是多种树吧……
Code：
#include<bits/stdc++.h>
using namespace std;
int n,m;
double down=0.997;//降温系数
double ansx,ansy,ansn,r;
struct node{
double x,y,r;
}b[15];
struct data{
double x,y;
}p[1005];
int getans(double x,double y){//可以定义成 int 是因为敌人都是整数个的
int res=0;
double f=r;
for(int i=1;i<=n;i++){
double xx=b[i].x,yy=b[i].y;//可以换，但是后一行会长很多
double tot=sqrt((xx-x)*(xx-x)+(yy-y)*(yy-y));//计算距离
f=min(f,tot-b[i].r);//计算最小值
}
for(int i=1;i<=m;i++){//和上一个循环差不多
double xx=p[i].x,yy=p[i].y;
double tot=sqrt((xx-x)*(xx-x)+(yy-y)*(yy-y));
if(tot<=f)res++;//如果在炸弹范围内就算被消灭了
}
return res;
}
void sa(){//模拟退火
double t=2667;//初始温度
while(t>1e-15){//终止温度
double nx=ansx+(rand()*2-RAND_MAX)*t;//随机生成下一个目标点
double ny=ansy+(rand()*2-RAND_MAX)*t;
double nnum=getans(nx,ny);//求函数值
double f=nnum-ansn;//计算 Delta T
if(f>0){//找到更优解
ansx=nx,ansy=ny;//替换答案及坐标
ansn=nnum;
}
else if(exp(-f/t)*RAND_MAX<rand()){//按概率更新答案坐标
ansx=nx,ansy=ny;//不需要更新最优答案
}
t*=down;//降温
}
}
int main(){
srand(114514+1919810);//玄学恶臭种子
srand(rand()+20070606);//还是玄学
srand(rand());
srand(rand());
srand(rand());
cin>>n>>m>>r;
for(int i=1;i<=n;i++)cin>>b[i].x>>b[i].y>>b[i].r;
for(int i=1;i<=m;i++){
cin>>p[i].x>>p[i].y;
ansx+=p[i].x,ansy+=p[i].y;
}
ansx/=m,ansy/=m;//求平均值逼近答案
ansn=getans(ansx,ansy);//求出初始答案
sa();//多跑几遍增加找到正确答案的概率
sa();
sa();
sa();
sa();
sa();
sa();
cout<<ansn;//直接输出就可以了
return 0;
}