[语言月赛202211] Zone Selection

Luogu
IDLGB3679
Time1000ms
Memory512MB
DifficultyP1
2022结构体语言月赛
在第五人格巅峰七阶及以上的排位赛中,需要进行区域选择。我们将在本题中形式化、推广化的解决区域选择问题。 在地图中,共有 $n$ 台密码机,第 $i$ 台密码机的坐标为 $(x_i,y_i)$。在推广化的游戏中,有 $k$ 名求生者。每名求生者可以选择一台密码机作为其出生点,我们称被选择的密码机为 **出生密码机**。 监管者共有 $T$ 个出生点可供选择。第 $i$ 个可能的出生点坐标为 $(x_i,y_i)$。此时,由于“封禁”天赋的存在,离监管者最远的密码机将不能被破译。 **如果多台密码机与监管者的距离相同且最远,“封禁”天赋将会封禁这几台密码机中标号最小的那一台。** 请问在该 $T$ 个出生点中,有多少出生点,可以使某一台 **出生密码机** 被封禁。 请注意:坐标点 $(x_1,y_1)$ 与坐标点 $(x_2,y_2)$ 之间的距离为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$。 ## Input 输入共 $n+T+k+1$ 行。 输入的第一行为三个整数 $n,k,T$。 接下来 $n$ 行,每行两个整数 $x_i,y_i$,表示一台密码机的坐标。 接下来 $k$ 行,每行两个整数 $x_i,y_i$,表示一名求生者选择出生密码机的坐标,保证该坐标在上面出现过。 接下来 $T$ 行,每行两个整数 $x_i,y_i$,表示监管者的一个出生点。 ## Output 输出一行一个整数,为答案。 [samples] ## Note **【样例 #1 解释】** 显然,第一台密码机和第四台密码机为**出生密码机**。 第一位监管者与位置在 $(-1, 0)$ 的第一台密码机距离最远,为 $4$。因此,第一台密码机被封禁。 第二位监管者与位置在 $(2, 0), (0, 2)$ 的第三、四台密码机距离相同且最远,为 $2$。根据上面提到的规则,第三台密码机被封禁。 被封禁的出生密码机为 $1$ 台。 **【数据规模与约定】** 对前 $10\%$ 的数据,保证 $n = k = 1$。 对前 $20\%$ 的数据,保证 $n, k, t \leq 10$。 对另外 $20\%$ 的数据,保证密码机与出生点的坐标中的 $x$ 均为 $0$。 对另外 $10\%$ 的数据,保证 $n = k$。 对另外 $10\%$ 的数据,保证 $T = 1$。 对于 $100\%$ 的数据范围 $1 \le k \le n \le 10^3, 1 \le T \le 10^3, 1 \le |x_i|,|y_i| \le 10^3$。
Samples
Input #1
4 2 2
-1 0
0 -1
2 0
0 2
-1 0
0 2
3 0
0 0
Output #1
1
API Response (JSON)
{
  "problem": {
    "name": "[语言月赛202211] Zone Selection",
    "description": {
      "content": "在第五人格巅峰七阶及以上的排位赛中,需要进行区域选择。我们将在本题中形式化、推广化的解决区域选择问题。 在地图中,共有 $n$ 台密码机,第 $i$ 台密码机的坐标为 $(x_i,y_i)$。在推广化的游戏中,有 $k$ 名求生者。每名求生者可以选择一台密码机作为其出生点,我们称被选择的密码机为 **出生密码机**。 监管者共有 $T$ 个出生点可供选择。第 $i$ 个可能的出生点坐标为 $(",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P1"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3679"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在第五人格巅峰七阶及以上的排位赛中,需要进行区域选择。我们将在本题中形式化、推广化的解决区域选择问题。\n\n在地图中,共有 $n$ 台密码机,第 $i$ 台密码机的坐标为 $(x_i,y_i)$。在推广化的游戏中,有 $k$ 名求生者。每名求生者可以选择一台密码机作为其出生点,我们称被选择的密码机为 **出生密码机**。\n\n监管者共有 $T$ 个出生点可供选择。第 $i$ 个可能的出生点坐标为 $(...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments