#X3679. Zone Selection
Zone Selection
题目描述
在第五人格巅峰七阶及以上的排位赛中,需要进行区域选择。我们将在本题中形式化、推广化的解决区域选择问题。
在地图中,共有 台密码机,第 台密码机的坐标为 。在推广化的游戏中,有 名求生者。每名求生者可以选择一台密码机作为其出生点,我们称被选择的密码机为 出生密码机。
监管者共有 个出生点可供选择。第 个可能的出生点坐标为 。此时,由于“封禁”天赋的存在,离监管者最远的密码机将不能被破译。
如果多台密码机与监管者的距离相同且最远,“封禁”天赋将会封禁这几台密码机中标号最小的那一台。
请问在该 个出生点中,有多少出生点,可以使某一台 出生密码机 被封禁。
请注意:坐标点 与坐标点 之间的距离为 。
输入格式
输入共 行。
输入的第一行为三个整数 。
接下来 行,每行两个整数 ,表示一台密码机的坐标。
接下来 行,每行两个整数 ,表示一名求生者选择出生密码机的坐标,保证该坐标在上面出现过。
接下来 行,每行两个整数 ,表示监管者的一个出生点。
输出格式
输出一行一个整数,为答案。
样例 #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 \le k \le n \le 10^3, 1 \le T \le 10^3, 1 \le |x_i|,|y_i| \le 10^3$。