A92005.「JSOI2016」炸弹攻击
NOI/NOI+/CTSC
通过率:0%
时间限制:1.00s
内存限制:256MB
题目描述
JYY 最近迷上了一款塔防游戏,在游戏里 JYY 除了建设建筑,还可以使用炸弹对屏幕上的敌人进行范围杀伤。
游戏地图可以简单认为是一个二维平面。JYY 建造了 N 个建筑,每个建筑都是一个圆,其中第 i 个建筑的圆心位于 (xi,yi) 且半径为 ri。地图上一共有 M 个敌人,一个敌人可以近似看成一个平面上的点,其中第 i 个敌人位于 (pi,qi)。JYY 可以使用一枚可以设置半径的炸弹,可以设置一个不超过 R 的范围,然后选择平面上的一个点引爆,范围内的所有敌人全部消灭。
当然,由于炸弹威力巨大,如果爆炸范围接触到 JYY 的建筑,那么 JYY 的建筑也会受到损伤。(注:如果炸弹的爆炸范围仅接触到了 JYY 建筑的边界,则不会对 JYY 的建筑造成损伤;如果敌人出现在了爆炸范围的边界,则该敌人被消灭)JYY 可以自由控制炸弹的爆炸地点和爆炸半径。作为一个保守的玩家,他希望在保证自己建筑毫发无损的情况下,消灭尽量多的敌人。
输入格式
第一行包含三个非负整数,分别为 N,M,R;
接下来 N 行,每行三个整数,其中第 i 行为 xi,yi,ri,表示第 i 个建筑的位置和半径。数据保证所有建筑不相交(但是有可能边界接触);
接下来 M 行,每行两个整数,其中第 i 行为 pi,qi,表示第 i 个敌人的位置。
输出格式
输出一行一个整数,表示 JYY 最多可以消灭的敌人数量。
输入输出样例
输入#1
1 5 3 0 0 1 3 3 -3 3 3 -3 3 0 0 3
输出#1
3
输入#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
说明/提示
对于 20% 的数据,满足 M=2;
对于另外 20% 的数据,满足 N=0;
对于另外 20% 的数据,满足 M≤50;
对于 100% 的数据,满足 0≤N≤10,0<M≤103,1≤R,ri≤2×104,∣pi∣,∣qi∣,∣xi∣,∣yi∣≤2×104。