#P2536. Gopher II

Gopher II

题目翻译

地鼠家族在成功躲避犬类威胁后,又面临新的捕食者——鹰。

现有 nn 只地鼠和 mm 个地鼠洞,每个地鼠和地鼠洞的位置坐标 (x,y)(x, y) 均不相同。一只鹰即将来袭,若某只地鼠未能在 ss 秒内抵达任意一个地鼠洞,它就会被鹰捕食。每个地鼠洞最多只能容纳一只地鼠。所有地鼠的移动速度均为 vv。地鼠家族需要制定一个逃生策略,使得被捕获的地鼠数量最少。

输入格式

  • 每个测试用例的第一行包含四个小于 100100 的正整数:nn(地鼠数量)、mm(地鼠洞数量)、ss(时间限制,秒)和 vv(地鼠速度,米/秒)。
  • 接下来的 nn 行给出每只地鼠的坐标;
  • 随后的 mm 行给出每个地鼠洞的坐标。
  • 所有距离单位为米,时间单位为秒,速度单位为米/秒。

输出格式

  • 对于每个测试用例,输出一行,表示无法逃脱的地鼠数量。

输入样例 1

2 2 5 10
1.0 1.0
2.0 2.0
100.0 100.0
20.0 20.0

输出样例 1

1