🐷大肚肚
CF-84C3

射击

1.0s💾 256MB

📋 题目描述

射击场上有 nn 个射击目标,每个目标都是圆形的,每个圆的中心都位于 OxOx 轴上。在一次训练中,共进行了 mm 次射击。你的任务是统计每个目标被射中了多少次。只要射击点坐标在圆内或者在圆的边界上,被视为射中目标。

📥 输入格式

第一行仅有一个整数 nn ( 1n1041 ≤ n ≤ 10^4 ) ,表示圆(即射击目标)的个数,编号从 11nn 。接下来的 nn 行依次给出 nn 个圆的参数。每个圆的圆心都位于 OxOx 轴上,每个圆的参数包括两个整数,即圆心坐标 xx ( 2×104x2×104-2×10^4 ≤ x ≤ 2×10^4 ) 和半径 rr ( 1r10001 ≤ r ≤ 1000 ) 。保证没有两个圆重合、相交或嵌套,但它们可以相互接触

之后的一行仅有一个整数 mm ( 1m2×1051 ≤ m ≤ 2×10^5 ),表示射击次数,随后的 mm 行依次给出第 11 到第 mm 次射击的信息,每行给出一次射击点在平面直角坐标系上的位置坐标,两个整数,即横坐标 xx 和纵坐标 yy ( 2×104x-2×10^4 ≤ x, y2×104y ≤ 2×10^4 ) 。

📤 输出格式

第一行仅有一个整数,表示命中的目标个数,第二行包含 nn 个整数,之中第 ii 个整数表示第 ii 个目标首次被命中的那一枪的编号,如果该目标没有被命中,则输出 " 1-1 "(不用引号括起来),两两之间用一个空格分隔。

📝 样例 1

输入
3
2 1
5 2
10 1
5
0 1
1 3
3 0
4 0
4 0
输出
2
3 3 -1

📝 样例 2

输入
3
3 2
7 1
11 2
4
2 1
6 0
6 4
11 2
输出
3
1 2 4

📚 来源

💡 题目讲解

1

理解题意

OxOx 轴上有 nn 个圆形靶子(圆心在 x 轴上,半径 rir_i)。进行了 mm 次射击,射击点 (x,y)(x,y) 可以在任意位置。

只要射击点落在圆内(含边界),就算命中。一个射击可以同时命中多个靶子(如果几个圆重叠)。

统计每个靶子被命中几次。

1 / 4