← 返回题目列表

Codeforces · 84/C

C. 冬季两项

中文机器翻译题面 查看原题

也许很多人都听说过冬季两项世界锦标赛已经结束了。尽管我们的英雄瓦莱拉本人并没有出席这场盛大的赛事,只是在电视上观看,但这让他非常兴奋,以至于他决定参加冬季两项项目。

当然,冬季两项运动与任何运动一样,在实践中被证明非常困难。这需要很多时间和精力。锻炼、锻炼、再锻炼——这就是瓦莱拉在冬季两项取得伟大成就的路上等待着的。

说到训练,大家可能都知道,每个职业冬季两项运动员都应该快速滑雪,在射击场精确射击。只有在这种情况下你才有希望取得成功,因为跑步和射击是冬季两项的两个主要组成部分。瓦莱拉的滑雪训练一直很刻苦,所以他跑得很快,但他的投篮精准度实在是不敢恭维。

在瓦莱拉准备比赛的一个冬季两项基地上,有一个巨大的步枪靶场,有n个目标。每个目标具有圆形形状,并且每个圆的中心位于Ox轴上。在最后一次训练中,瓦莱拉总共投篮了 m 次。为了让他更容易监控自己的结果,一位相当知名的程序员(当然就是你)受委托编写一个程序,该程序将显示瓦莱拉击中了多少个目标以及击中了哪些目标。更具体地说,对于每个目标,程序必须打印第一次成功射击的次数(在目标中),如果没有击中,则打印“-1”。如果射击在圆圈内或其边界上,则视为击中目标。瓦莱拉指望着你,也许,多亏了你,他有一天会赢得国际比赛。

输入

输入文件的第一行包含整数 n (1 ≤ n ≤ 104),它是目标的数量。接下来的 n 行包含目标的描述。每个目标都是一个圆心位于 Ox 轴上的圆。每个圆由其中心坐标 x (- 2·104 ≤ x ≤ 2·104) 及其半径 r (1 ≤ r ≤ 1000) 给出。保证没有两个目标重合、相交或嵌套,但它们可以相互接触。

下一行包含整数 m (1 ≤ m ≤ 2·105),它是射击次数。接下来的 m 行包含镜头的描述,镜头是平面上的点,由坐标 x 和 y 给出(- 2·104 ≤ x,y ≤ 2·104)。

输入中的所有数字均为整数。

目标和射击按照输入顺序从 1 开始编号。

输出

在第一行打印一个数字,即瓦莱拉击中的目标数量。在每个目标的第二行打印其第一次命中的编号,如果该编号不存在,则打印“-1”(不带引号)。用空格分隔数字。

示例

输入 #1

3
2 1
5 2
10 1
5
0 1
1 3
3 0
4 0
4 0

输出 #1

2
3 3 -1

输入 #2

3
3 2
7 1
11 2
4
2 1
6 0
6 4
11 2

输出 #2

3
1 2 4