#P17824. [Ontak2022]GAL
[Ontak2022]GAL
题目描述
平面上有 颗奇异恒星和 个黑洞。所有恒星始终以每单位时间移动1个单位距离的速度运动,可以在任意时刻瞬间改变为任意方向。
一颗恒星到达某个黑洞时,会立即出现在任意一个黑洞处,包括原来的黑洞。不能预知运动方向和传送目的地;我们考虑最坏的情形。
求最早可能发生两颗恒星碰撞的时刻。
输入格式
第一行两个整数 。接下来 行,每行两个整数 。前 行是恒星位置,后 行是黑洞位置。
输出格式
输出最早可能碰撞的时间。与标准答案的绝对误差不得超过 。
数据范围
,;;任意两个天体初始坐标都不同。
子任务
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | n,m≤5000 | 17 |
| 2 | n≤5000 | 21 |
| 3 | m≤100 | 19 |
| 4 | 所有 xᵢ≤100 | 15 |
| 5 | 无额外限制 | 28 |
样例 1
输入:
3 2
1 1
7 1
4 6
5 7
8 2
输出:
1.41421356237