#B1506. 最远点合法的起点数

最远点合法的起点数

【题目描述】

地图中共有 nn 台密码机,第 ii 台密码机的坐标为 (xi,yi)(x_i,y_i)。

有 kk 名求生者,每名求生者选择一台密码机作为出生点,被选择的密码机称为出生密码机。接下来有 TT 个监管者出生点。

对于每个监管者出生点,需要封禁距离该出生点最远的密码机。如果有多台密码机距离相同且都是最远的,则封禁其中编号最小的密码机。

请计算在这 TT 个监管者出生点中,有多少个出生点会封禁一台出生密码机。

两点 (x1,y1)(x_1,y_1) 和 (x2,y2)(x_2,y_2) 的距离为 (x1−x2)2+(y1−y2)2\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}。

【输入描述】

输入共 n+T+k+1n+T+k+1 行。

第一行输入三个整数 n,k,Tn,k,T,分别表示密码机数量、出生密码机数量和监管者 出生点数量。

接下来 nn 行,每行输入一台密码机的坐标 (xi,yi)(x_i,y_i)。

接下来 kk 行,每行输入一台出生密码机的坐标。保证这些坐标在前面出现过。

接下来 TT 行,每行输入一个监管者出生点坐标。

保证:

  • 1≤k≤n≤10001\le k\le n\le1000;
  • 1≤T≤10001\le T\le1000;
  • 坐标满足 −1000≤xi,yi≤1000-1000\le x_i,y_i\le1000;
  • 每个出生密码机坐标都与某台密码机的坐标完全相同。

【输出描述】

输出一行一个整数,表示会封禁出生密码机的监管者出生点数量。

【样例 1】

【样例 1 输入】

4 2 2
-1 0
0 -1
2 0
0 2
-1 0
0 2
3 0
0 0

【样例 1 输出】

1

【样例 1 解释】

第一台和第四台密码机是出生密码机。

对于监管者出生点 (3,0)(3,0),第一台密码机距离为 44,是最远密码机,因此该出生点会封禁一台出生密码机。

对于监管者出生点 (0,0)(0,0),第三台和第四台密码机距离相同且最远,根据“距离相同则选择编号最小”的规则,最终封禁第三台密码机。

只有一个监管者出生点封禁了出生密码机,因此答案为 11。

【数据规模与约定】

测试点编号 分数 特殊性质
1 10 n=k=1n=k=1
2 n,k,T≤10n,k,T\le10
3 ~ 4 20 密码机与出生点的横坐标均为 00
5 10 n=kn=k
6 T=1T=1
7 ~ 10 40 无特殊性质