#P4852. [Jsoi2016]炸弹攻击

    ID: 3971 传统题 5000ms 512MiB 尝试: 318 已通过: 54 难度: 9 上传者: 标签>难度分类提高+/省选-枚举与搜索暴力枚举计算几何点积排序与序列处理环形区间拆分扫描线事件同坐标排序CF2600杂项随机化

[Jsoi2016]炸弹攻击

题目背景

JYY 在一款塔防游戏里修建建筑,也可以用炸弹攻击敌人。

题目描述

地图是一个二维平面。JYY 的 NN 个建筑各占一块圆形区域。第 ii 个建筑的圆心是 (xi,yi)(x_i,y_i),半径为 rir_i。地图上还有 MM 个敌人,每个敌人视为一个点,第 ii 个位于 (pi,qi)(p_i,q_i)。

JYY 可以选择平面上的一个位置引爆一枚炸弹,并设置不超过 RR 的非负实数爆炸半径。爆炸范围内及其边界上的敌人都会被消灭。爆炸范围若侵入建筑,会损坏建筑。爆炸范围只与建筑的边界相切时,建筑不会受损。

求在所有建筑毫发无损的前提下,一枚炸弹最多能消灭多少个敌人。

输入格式

第一行三个整数 N,M,RN,M,R。

接下来 NN 行,每行三个整数 xi,yi,rix_i,y_i,r_i,表示一个建筑。建筑内部互不相交,边界可以相切。

接下来 MM 行,每行两个整数 pi,qip_i,q_i,表示一个敌人的位置。

输出格式

输出一行一个整数,表示最多能消灭的敌人数。

样例 #1

输入 #1

1 5 3
0 0 1
3 3
-3 3
3 -3
3 0
0 3

输出 #1

3

样例 #2

输入 #2

4 10 100
0 0 3
10 0 3
10 10 3
0 10 3
0 4
0 5
0 6
5 3
5 -3
5 5
6 7
3 6
10 4
8 4

输出 #2

5

样例 1 解释

一种最优做法是在 (3,3)(3,3) 引爆半径为 33 的炸弹。

数据范围

  • 对于 20%20\% 的数据,M=2M=2。
  • 对于另外 20%20\% 的数据,N=0N=0。
  • 对于另外 20%20\% 的数据,M≤50M\le 50。
  • 对于 100%100\% 的数据,0≤N≤100\le N\le 10,0<M≤1030<M\le 10^3,1≤R,ri≤20 0001\le R,r_i\le 20\,000,∣pi∣,∣qi∣,∣xi∣,∣yi∣≤20 000|p_i|,|q_i|,|x_i|,|y_i|\le 20\,000。

原题册(第 6—7 页为本题)