#P4852. [Jsoi2016]炸弹攻击
[Jsoi2016]炸弹攻击
题目背景
JYY 在一款塔防游戏里修建建筑,也可以用炸弹攻击敌人。
题目描述
地图是一个二维平面。JYY 的 个建筑各占一块圆形区域。第 个建筑的圆心是 ,半径为 。地图上还有 个敌人,每个敌人视为一个点,第 个位于 。
JYY 可以选择平面上的一个位置引爆一枚炸弹,并设置不超过 的非负实数爆炸半径。爆炸范围内及其边界上的敌人都会被消灭。爆炸范围若侵入建筑,会损坏建筑。爆炸范围只与建筑的边界相切时,建筑不会受损。
求在所有建筑毫发无损的前提下,一枚炸弹最多能消灭多少个敌人。
输入格式
第一行三个整数 。
接下来 行,每行三个整数 ,表示一个建筑。建筑内部互不相交,边界可以相切。
接下来 行,每行两个整数 ,表示一个敌人的位置。
输出格式
输出一行一个整数,表示最多能消灭的敌人数。
样例 #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 解释
一种最优做法是在 引爆半径为 的炸弹。
数据范围
- 对于 的数据,。
- 对于另外 的数据,。
- 对于另外 的数据,。
- 对于 的数据,,,,。