#4025. 可恶的雾霾天

    ID: 4025 传统题 1000ms 32MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>ACM俱乐部算法基础练习赛-ACM俱乐部算法基础练习赛(4)排序贪心二分近似算法

可恶的雾霾天

可恶的雾霾天

题目描述

最近雾霾侵袭,小明出门都带上口罩了。有一天小明出门办事,办完事后发现雾霾天愈发严重,于是他想马上坐出租车回家。
他发现附近有n个人要坐出租车,并且有m辆出租车停在附近等着拉客。每个人的步行速度都是v,现在给你n个人和m辆出租车的位置,请你计算出所有人都坐上出租车最少需要多长时间。注意一辆出租车只能坐一个人。

输入说明

输入包含多组测试数据。
每组输入的第一行是两个整数n(0<n<=100)和m(n<=m<=100)。
接下来n行,每行输入两个整数Xi和Yi(0<=Xi,Yi<=10000),表示第i个人的位置。
然后再输入m行,每行输入两个整数xi和yi(0<=xi,yi<=10000),表示第i辆出租车的位置。
最后输入一个实数v(0.00001<v<=10000),表示每个人的步行速度。

输出说明

对于每组输入,输出所有人都坐上出租车最少需要多长时间,结果保留两位小数。

样例

输入

2 3
0 0
0 1
1 0
1 1
2 1
1

输出

1.00