Znzryb's Blog
0%

2026 杭电春季联赛 2——1005-守矢晨风

Posted on

题目大意

题目描述

给定平面上 nn 个圆形区域，第 ii 个圆的圆心坐标为 (pi,qi)(p_i, q_i)，半径为 rir_i（保证 ri≤30r_i \le 30）。

给定 mm 次询问，每次询问给出一个四边平行于坐标轴的矩形区域，指定了其左下角顶点坐标 (xi,1,yi,1)(x_{i,1}, y_{i,1}) 和右上角顶点坐标 (xi,2,yi,2)(x_{i,2}, y_{i,2})。对于每次询问，需要计算出在给定的 nn 个圆中，有多少个圆与该矩形区域存在至少一个公共点。

数据范围

测试用例数量 tt 满足 1≤t≤10001 \le t \le 1000。
每次测试中的圆的个数 nn 满足 1≤n≤1.5×1061 \le n \le 1.5 \times 10^6，询问的个数 mm 满足 1≤m≤1041 \le m \le 10^4。
对于全部测试用例，保证 ∑n≤3×106\sum n \le 3 \times 10^6，∑m≤2×104\sum m \le 2 \times 10^4。
坐标与半径范围：1≤pi,qi≤1091 \le p_i, q_i \le 10^9，1≤ri≤301 \le r_i \le 30，1≤xi,1≤xi,2≤1091 \le x_{i,1} \le x_{i,2} \le 10^9，1≤yi,1≤yi,2≤1091 \le y_{i,1} \le y_{i,2} \le 10^9。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
4 1
1 1 1
7 1 2
5 3 2
1 2 1
2 2 6 4
8 3
5 6 4
7 7 4
3 3 2
1 8 5
10 1 2
1 8 1
7 2 2
5 4 5
9 1 10 5
3 1 6 3
5 1 9 5

样例输出

1
2
3
4
3
4
4
7

样例解释

在第一组测试数据中，共有 44 个圆和 11 次询问。询问给定的矩形左下角坐标为 (2,2)(2, 2)，右上角坐标为 (6,4)(6, 4)。经过判断，该矩形与输入的第 22 个圆、第 33 个圆以及第 44 个圆（总计三个圆形）存在公共点，因此该次询问的答案为 33。第二组测试数据同理，分别输出对应矩形内包含公共点的圆的数量。

思路讲解

AC代码

心路历程（WA，TLE，MLE……）