抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

洛谷P2074 危险区域

题意简述

一个矩阵上有一些点,每个点影响范围为 $T$,输出影响力最大的点能影响的范围。

输入:

  • 矩阵的尺寸 $N$,$M$,点的个数 $K$ 与影响范围 $T$。($N,M<=100000$)
  • 每个点的坐标。

输出:

  • 最大的范围。

题目分析

样例

首先暴力的解法并不难想,枚举矩阵中的每个坐标并判断与点的坐标是否小于等于 $T$ ,然后记录数量输出最小值即可。

但因为 $N$ 和 $M$ 的范围很大,一个个枚举肯定会超时,所以我们要想办法缩小枚举范围。

分析

经过观察我们发现,只有紫色区域是需要进行枚举的,而紫色区域的范围即圆所在的正方形和矩形的公共部分。

还有一个小优化,如果圆所在的正方形完全被包括在了矩形内,因为它没有任何地方被浪费,那么它肯定是最优解,直接输出这个解即可。

详情请见代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
int N, M; //矩阵的大小
int K; //点的个数
int T; //影响范围
int a, b; //每个点的坐标
int num; //当前的解
int ans; //最终的解
inline bool inc() //判断是否完全被包括
{
return (a - T >= 0) and (a + T <= N) and (b - T >= 0) and (b + T <= M);
}
inline double dis(const int &x1, const int &x2, const int &y1, const int &y2) //计算两点距离
{
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int main()
{
cin >> N >> M >> K >> T;
while (K--)
{
num = 0;
cin >> a >> b;

/*缩小范围后的枚举*/
/**
* a-T为正方形的左边
* a+T为正方形的右边
* b-T为正方形的上边
* b+T为正方形的下边
*/
for (int i = max(1, a - T); i <= min(N, a + T); ++i)
{
for (int j = max(1, b - T); j <= min(M, b + T); ++j)
{
if (dis(i, a, j, b) <= T) //满足条件的统计
{
num++;
}
}
}

if (inc())
{
cout << num; //如果必定是最优解那么直接输出
return 0;
}

ans = max(ans, num);
}
cout << ans;
return 0;
}