#X3679. Zone Selection

Zone Selection

题目描述

在第五人格巅峰七阶及以上的排位赛中,需要进行区域选择。我们将在本题中形式化、推广化的解决区域选择问题。

在地图中,共有 nn 台密码机,第 ii 台密码机的坐标为 (xi,yi)(x_i,y_i)。在推广化的游戏中,有 kk 名求生者。每名求生者可以选择一台密码机作为其出生点,我们称被选择的密码机为 出生密码机

监管者共有 TT 个出生点可供选择。第 ii 个可能的出生点坐标为 (xi,yi)(x_i,y_i)。此时,由于“封禁”天赋的存在,离监管者最远的密码机将不能被破译。

如果多台密码机与监管者的距离相同且最远,“封禁”天赋将会封禁这几台密码机中标号最小的那一台。

请问在该 TT 个出生点中,有多少出生点,可以使某一台 出生密码机 被封禁。

请注意:坐标点 (x1,y1)(x_1,y_1) 与坐标点 (x2,y2)(x_2,y_2) 之间的距离为 (x1x2)2+(y1y2)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,yix_i,y_i,表示一台密码机的坐标。

接下来 kk 行,每行两个整数 xi,yix_i,y_i,表示一名求生者选择出生密码机的坐标,保证该坐标在上面出现过。

接下来 TT 行,每行两个整数 xi,yix_i,y_i,表示监管者的一个出生点。

输出格式

输出一行一个整数,为答案。

样例 #1

样例输入 #1

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

样例输出 #1

1

提示

【样例 #1 解释】

显然,第一台密码机和第四台密码机为出生密码机

第一位监管者与位置在 (1,0)(-1, 0) 的第一台密码机距离最远,为 44。因此,第一台密码机被封禁。

第二位监管者与位置在 (2,0),(0,2)(2, 0), (0, 2) 的第三、四台密码机距离相同且最远,为 22。根据上面提到的规则,第三台密码机被封禁。

被封禁的出生密码机为 11 台。

【数据规模与约定】

对前 10%10\% 的数据,保证 n=k=1n = k = 1

对前 20%20\% 的数据,保证 n,k,t10n, k, t \leq 10

对另外 20%20\% 的数据,保证密码机与出生点的坐标中的 xx 均为 00

对另外 10%10\% 的数据,保证 n=kn = k

对另外 10%10\% 的数据,保证 T=1T = 1

对于 100%100\% 的数据范围 $1 \le k \le n \le 10^3, 1 \le T \le 10^3, 1 \le |x_i|,|y_i| \le 10^3$。