洛谷P3717探测器解题报告

- 日理万妓 2023-07-07 15:55 8阅读 0赞

以样例1中的数据为例，共有5 \* 5个格子。有两个探测器A和B，探测距离为1个格子。  
A能探测到的点为它本身、两个绿色的点、两个黑色的点。B能探测到的点为它本身、两个绿色的点、两个紫色的点。  
注意，两个黑色的点既能被A探测到，也能被B探测到，只能算一次，不要重复计算。  
所以总共有8个点能被探测到：俩黑色点、俩紫色点、俩绿色点、点A、点B。  
其他的点都不能被探测到，比如C点与B点的距离是2，不能被B探测到；C点与A点的距离是根号2，也不能被A探测到。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaXNodV96aGVuZw_size_16_color_FFFFFF_t_70]  
算法的思路是把所有的点都枚举一遍，点与探测器的距离可以用勾股定理算出。AC代码如下 ：

#include <iostream>
    using namespace std;
    
    struct detector //探测器
    {
        int x;      //行坐标
        int y;      //列坐标
    };
    
    int main()
    {
        int n, m, r;
        cin >> n >> m >> r;
        detector det[m + 1]; 
        for(int i = 1; i <= m; i++)
        {
            cin >> det[i].x >> det[i].y;
        }
    
        int cnt = 0;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                for(int k = 1; k <= m; k++)
                {
                    if((i - det[k].x) * (i - det[k].x) + (j - det[k].y) * (j - det[k].y) <= r * r)
                    {
                        cnt++;
                        break;  //只要被任意一个点探测到，就要退出循环，不退出会导致计算重复
                    }
                }
            }
        }
    
        cout << cnt;
        return 0;
    }

> =======================================  
> 了解信息学奥赛请加微信307591841或QQ群581357582

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaXNodV96aGVuZw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/202002241128432.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaXNodV96aGVuZw==,size_16,color_FFFFFF,t_70