#P8061. [JSOI2016] 炸弹攻击1 - 数据加强版

    ID: 7199 远端评测题 100~3000ms 512MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>计算几何2015离散化扫描ACM_ICPC

[JSOI2016] 炸弹攻击1 - 数据加强版

题目背景

JYY 最近迷上了一款塔防游戏,在游戏里 JYY 除了建设建筑,还可以使用炸弹对屏幕上的敌人进行范围杀伤。

题目描述

游戏地图可以简单认为是一个二维平面。JYY 建造了 NN 个建筑,每个建筑都是一个圆,其中第 ii 个建筑的圆心位于 (xi,yi)(x_i,y_i) 且半径为 rir_i。地图上一共有 MM 个敌人,一个敌人可以近似看成一个平面上的点,其中第 ii 个敌人位于 (pi,qi)(p_i,q_i)。JYY 可以使用一枚可以设置半径的炸弹,可以设置一个不超过 RR 的范围,然后选择平面上的一个点引爆,范围内的所有敌人全部消灭。

当然,由于炸弹威力巨大,如果爆炸范围接触到 JYY 的建筑,那么 JYY 的建筑也会受到损伤。(注:如果炸弹的爆炸范围仅接触到了 JYY 建筑的边界,则不会对 JYY 的建筑造成损伤;如果敌人出现在了爆炸范围的边界,则该敌人被消灭)JYY 可以自由控制炸弹的爆炸地点和爆炸半径。作为一个保守的玩家,他希望在保证自己建筑毫发无损的情况下,消灭尽量多的敌人。

输入格式

第一行包含三个非负整数,分别为 N,M,RN,M,R

接下来 NN 行,每行三个整数,其中第 iixi,yi,rix_i,y_i,r_i,表示第 ii 个建筑的位置和半径。数据保证所有建筑不相交(但是有可能边界接触);

接下来 MM 行,每行两个整数,其中第 ii 行为 pi,qip_i,q_i,表示第 ii 个敌人的位置。任意两个敌人的位置不同,且敌人不会出现在建筑里。

输出格式

输出一行一个整数,表示 JYY 最多可以消灭的敌人数量。

1 3 3
0 0 1
3 3
-3 3
3 -3
1
1 5 3
0 0 1
3 3
-3 3
3 -3
3 0
0 3
3
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
5

提示

对于 100%100\% 的数据,满足 1N101\leq N\leq 101M20001\leq M\leq 20001R,ri2×1041\leq R,r_i\leq 2\times 10^4pi,qi,xi,yi2×104|p_i|,|q_i|,|x_i|,|y_i|\leq 2\times 10^4

数据来源于 NAIPC 2015 Problem A - Area of Effect,并有部分自造新数据。