← 返回题目列表

Codeforces · 1662/K

K. 流行病限制

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

在国外生活了很长时间后,您决定搬回意大利并必须找到一个住处,但由于全球大流行的持续,事情并不那么容易。

你的三个朋友 Fabio、Flavio 和 Francesco 住在坐标分别为 $$$(x_1, y_1)、(x_2, y_2)$$$ 和 $$$(x_3, y_3)$$$ 的点。由于疫情期间的行动限制,会议仅限 $$$3$$$ 人,因此您一次只能与 $$$2$$$ 朋友见面。此外,为了遏制感染蔓延,当局还采取了以下额外措施:每次会议,每位与会者从居住地到会议地点的行程总和不得超过$$$r$$$。

如果存在一个居住地,允许您举行涉及您和您的两个朋友的三场可能的会议,$$$r$$$(可以是任何非负实数)的最小值是多少?请注意,所选的居住地点不需要具有整数坐标。

输入

第一行包含两个整数 $$$x_1, y_1$$$ ($$$-10^4 \le x_1, y_1 \le 10^4$$$) — 你的朋友 Fabio 的房子的坐标。

第二行包含两个整数 $$$x_2, y_2$$$ ($$$-10^4 \le x_2, y_2 \le 10^4$$$) — 你的朋友 Flavio 的房子的坐标。

第三行包含两个整数 $$$x_3, y_3$$$ ($$$-10^4 \le x_3, y_3 \le 10^4$$$) — 你的朋友 Francesco 的房子的坐标。

保证你的三个朋友住在不同的地方(即三个点 $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$, $$$(x_3, y_3)$$$ 保证不同)。

输出

打印 $$$r$$$ 的最小值,它可以让你找到满足上述条件的居住地。如果您的答案的绝对或相对误差不超过 $$$10^{-4}$$$,则视为正确。

正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$$$ 时,您的答案才会被接受。

示例

输入 #1

0 0
5 0
3 3

输出 #1

5.0686143166

输入 #2

-1 0
0 0
1 0

输出 #2

2.0000000000

注意

在第一个样本中,Fabio、Flavio 和 Francesco 分别居住在坐标为 $$$(0,0)$$$、$$$(5,0)$$$ 和 $$$(3,3)$$$ 的点。最佳居住地(由下图中的温室表示)位于坐标 $$$(2.3842..., 0.4151...)$$$ 的点。

在第二个样本中,线段 $$$\{(x,0):\ -1 \leq x \leq 1 \}$$$ 上的任意点都是最佳居住地。