← 返回题目列表

Codeforces · 744/D

D. 红牛画圆

中文机器翻译题面 查看原题

红牛真的很喜欢红色。红牛不喜欢蓝色。

红牛站在一个无限的视野中,有n个红点和m个蓝点。

Hongcow 想要在字段中画一个圆,使得该圆包含至少一个红点,并且不包含蓝点。恰好位于圆边界上的点可以算作内部或外部。

计算满足此条件的最大圆的半径。如果这个圆可以有任意大的尺寸,则打印 - 1。否则,如果相对或绝对误差最多为 10 - 4,您的答案将被接受。

输入

输入的第一行将包含两个整数 n, m (1 ≤ n, m ≤ 1, 000)。

接下来的 n 行将包含两个整数 xi, yi (1 ≤ xi, yi ≤ 104)。这表示红点的坐标。

接下来的 m 行将包含两个整数 xi, yi (1 ≤ xi, yi ≤ 104)。这表示蓝点的坐标。

没有两个点具有相同的坐标。

输出

如果圆可以具有任意大小,则打印 - 1。否则,打印一个浮点数,表示满足条件的最大半径圆。如果您的答案的绝对或相对误差不超过 10 - 4,则视为正确。

也就是说,假设您的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-4}$$,检查程序将认为您的答案正确。

示例

输入 #1

2 5
2 3
3 4
1 1
1 4
4 2
4 7
2 5

输出 #1

3.5355338827

输入 #2

1 6
3 3
1 5
5 4
2 1
3 4
4 2
1 3

输出 #2

1.5811388195

输入 #3

2 2
2 2
3 3
1 1
4 4

输出 #3

-1

注意

这是第一个样本的图片

这是第二个样本的图片