#P17824. [Ontak2022]GAL

    ID: 16767 传统题 500~5000ms 512MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>计算几何扫描线数据结构CF2000排序算法基础数学

[Ontak2022]GAL

题目描述

平面上有 nn 颗奇异恒星和 mm 个黑洞。所有恒星始终以每单位时间移动1个单位距离的速度运动,可以在任意时刻瞬间改变为任意方向。

一颗恒星到达某个黑洞时,会立即出现在任意一个黑洞处,包括原来的黑洞。不能预知运动方向和传送目的地;我们考虑最坏的情形。

求最早可能发生两颗恒星碰撞的时刻。

输入格式

第一行两个整数 n,mn,m。接下来 n+mn+m 行,每行两个整数 xi,yix_i,y_i。前 nn 行是恒星位置,后 mm 行是黑洞位置。

输出格式

输出最早可能碰撞的时间。与标准答案的绝对误差不得超过 10−610^{-6}。

数据范围

2≤n≤5000002\le n\le500000,0≤m≤5000000\le m\le500000;1≤xi,yi≤1091\le x_i,y_i\le10^9;任意两个天体初始坐标都不同。

子任务

子任务 附加限制 分值
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