#1564. [语言月赛202211] Zone Selection

[语言月赛202211] 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) 之间的距离为 (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,yix_i,y_i,表示一台密码机的坐标。

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

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

输出格式

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

样例

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

题目来源:洛谷 B3679