/ Vijos / 题库 /

地鼠

地鼠

时间限制:1秒  内存限制:256M


【题目描述】

  地鼠家族面临着一个新的威胁——猎食者。

  地鼠家族一共有\(N\)个地鼠和\(M\)个鼠洞,每个都位于不同的\((x, y)\)坐标中。假如有地鼠在发觉危险以后\(s\)秒内都没有回到鼠洞里的话,就可能成为老鹰的食物。当然了,一个鼠洞只能拯救一只地鼠的命运,所有地鼠都以相等的速度\(v\)移动。地鼠家族需要设计一种策略,使得老鹰来时,易受攻击的地鼠数量最少。

【输入格式】

  本题有多组数据。第 1 行为测试数据组数\(T(T\le 50)\)。
  对于每组数据,第一行 4 个整数 \(n, m, s和v(n, m \le 100)\)。以后\(n\)行为地鼠的坐标,以后\(m\)行为鼠洞的坐标。距离的单位是m,时间的单位是s,速度的单位是m/s。

【输出格式】

  对于每组数据输出一行,为易受攻击的地鼠的数量。

【输入输出样例1】

 Input

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

 Output

1

【测试点性质】

  对于100%的数据,\(T\le 50,n,m\le 100\)。

【来源】

  Mr.he

信息

ID
3275
难度
(无)
分类
图结构 | 二分图二分图匹配 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
2
上传者