题解 P2074 【危险区域】

Atmizz · 2019-04-17 09:08:00 · 题解

枚举！！！这个最简单（因为我不会其他的。。）

提醒一下：如果您还没看题的话，请先回去看题，题目有点难以理解，我第一遍就理解错了。

• 恐怖组织只有一个炸弹（真穷）；
• 控制炸弹范围，避免超范围（有点难想到，我是借鉴了一位dalao的思路）。

输入一个街区坐标，然后就开始枚举街区，看是否在范围内。尽量不要开数组，因为数据范围大，容易爆空间，连编译都不过（手动滑稽）。

再就是，两点之间的距离公式->

sqrt((x-a)*(x-a)+(y-b)*(y-b))

初中的知识点，必须会啊！！！！这个题与P3717 cover类似，大家可以做一下。

再一个，此题容易超时，容易得50分（实践出真知，我实践了），建议大家使用函数计算距离。

double dis(int x,int y,int a,int b)//取距离函数，很重要 
{
    return sqrt((x-a)*(x-a)+(y-b)*(y-b));//两点之间距离公式 
}

好，该说的的都说完了，上code：

#include<cstdio>//不建议使用万能头。。 
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,k,t,x,y,ans,maxn=0;//ans表示一个炸弹可以炸的街道，maxn取最大的 
double dis(int x,int y,int a,int b)//取距离函数，很重要 
{
    return sqrt((x-a)*(x-a)+(y-b)*(y-b));//两点之间距离公式 
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&k,&t);//输入 
    for(int q=1;q<=k;q++) {
        ans=0;//不要忘了初始化 
        scanf("%d%d",&x,&y);//线上计算 
        for(int i=max(x-t,1);i<=min(n,x+t);i++) {//借鉴的大佬的思路，特别是这里 
            for(int j=max(y-t,1);j<=min(m,y+t);j++) {
                if(dis(i,j,x,y)<=t)//小于爆炸范围 
                    ans++;//计数器加加 
            }
        }
        if(maxn<ans)//取最大值 
            maxn=ans;
    }
    printf("%d",maxn);//输出 
    return 0;//完美の结束！！！ 
}