← 返回题目列表

AtCoder · arc010_4

D. 信息传播

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

問題文

AtCoder 青木君是一名在国家秘密情报部门工作并从事情报活动的年轻人。

这次青木君的任务如下。
  • 青木君是 2 致所有散落在次元坐标上的朋友 AtCoder 必须传达国家机密信息。
  • 然而, 2 在次元坐标上,不仅有朋友,还有来自敌国的间谍。
  • 当青木君向他的朋友传达机密信息时,收到信息的朋友通过扬声器传播信息(即使它是机密信息!)
  • 通过扬声器传播信息,是指将信息传递给以自己为中心的同心圆内的所有“人”(半径任意,扬声器的音量可以调节)。
  • 收到信息的朋友也通过音箱传播信息,信息链式传递。
  • 当然,机密信息绝对不能传递给间谍。

为了完成这个任务,青木君必须前往他所有朋友的所在地。
  1. 传达机密信息
  2. 砸碎你拿着的扬声器。
  3. “不要泄露机密信息!”

这个 3 我希望我能做一件事,但不幸的是我没有时间去所有朋友的地方。

因此,青木君决定利用朋友们通过扬声器传播信息的倾向,有效地传达机密信息。
如果青木君想将机密信息传达给所有朋友而不泄露给间谍,他至少必须向多少个朋友传达机密信息?

入力

输入将以以下格式从标准输入给出。
N
f_{x1} f_{y1}
f_{x2} f_{y2}
:
:
f_{xN} f_{yN}
M
s_{x1} s_{y1}
s_{x2} s_{y2}
:
:
s_{xM} s_{yM}
  • 1 行是一个整数,表示同伴的数量。 给出 N , 1≦N≦5,000 满意。
  • 2 在 N+1 至行 N 行给出了同伴的位置信息。 给定同伴的
    1. f_{xi} 为 i 第二个给定的同伴 X 坐标。 满足
    2. f_{yi} 为 i 第二个给定的同伴 Y 坐标。 满足
    3. i 为 1≦i≦N , f_{xi} 和 f_{yi} 分别是 它是满足 -10^9≦f_{xi} , f_{yi}≦10^9 的整数。
  • N+2 行是一个整数,表示间谍的数量。 M , 0≦M≦100,000 满意。
  • N+2 在 N+M+2 至行 M 行给出了间谍的位置。 给定间谍的
    1. s_{xj} 为 j 给出的间谍 X 坐标。 满足
    2. s_{yj} 为 j 给出的间谍 Y 坐标。 满足
    3. j 为 1≦j≦M , s_{xj} 和 s_{yj} 分别是 它是满足 -10^9≦s_{xj} , s_{yj}≦10^9 的整数。
  • 多人不能在同一坐标处重叠。 当
  • M>1,000 时,间谍保证是随机分布的。 如果仅对满足

部分点

  • 0≦N≦10 的输入给出正确答案,则部分点为 10 点。 如果正确答案是满足
  • 0≦N≦30 的输入给出正确答案,则部分点为 50 点。 如果正确答案是满足

出力

打印需要传达信息的最少人数。
输出应发送到标准输出,并在末尾添加换行符。 如果我可以告诉我的朋友

入力例 1

3
1 1
1 2
2 1
0

出力例 1

1
  • 座標 (1, 1) , 3 你可以告诉你所有的朋友。 来自坐标

入力例 2

2
1 1
1 2
1
2 1

出力例 2

1
  • 座標 (1, 2) , 2 你可以告诉你所有的朋友。 来自坐标
  • 座標 (1, 1) 的朋友 如果你试图告诉 (1, 2) 中的朋友,你总会被间谍发现。 如果你可以告诉你的朋友

入力例 3

5
1 1
1 2
2 3
3 3
5 3
2
2 1
4 4

出力例 3

2
  • 座標 (2, 3) 坐标 (1, 2) 中的好友和坐标 您可以通过 (3, 3) 向您的朋友发送信息。
  • 然后是坐标 来自朋友的坐标: (1, 2) 该信息将传播给您的朋友 (1, 1) 。 您需要通过
  • 座標 (5, 3) 向您的朋友传达更多信息。

入力例 4

10
-10 5
2 9
-4 4
10 -9
8 3
5 6
4 -5
6 8
-8 10
-4 -2
10
-1 2
-2 -7
9 -3
-5 5
6 -10
-10 9
7 4
2 1
-10 1
-5 2

出力例 4

8