← 返回题目列表

Codeforces · 696/F

F. ...达利!

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

巴尼终于找到了那个人,一位名叫莱安娜的美丽的年轻女士。问题是,莱安娜和巴尼被困在洛斯勋爵的城堡里。这座城堡的形状是 n 点的凸多边形。与德莫纳塔世界中的大多数城堡一样,这座城堡没有天花板。

巴尼和莱安娜有一个逃跑计划,但需要一些几何知识,所以他们请求你的帮助。

巴尼知道恶魔是有组织的并且排成一排。他和莱安娜想要等待适当的时机,所以他们需要留意恶魔。他们每个人都想呆在城堡内的某个点(可能在边缘或角落),也可能呆在同一个位置。他们都想选择一个实数 r 并观察每个点周围半径为 r 的圆中的所有点(这两个圆可能重叠)。

我们说巴尼和莱安娜正在仔细观察当且仅当对于多边形的每条边,至少其中一个可以看到该边所在线上的至少一个点,因此这个点可能不在边上,但它应该在边的线上。形式上,每条边缘线应至少与两个圆之一具有至少一个公共点。

r 越大,他们需要的能量和注意力就越多。所以他们要求你告诉他们r的最小值,以便他们可以仔细观察。

输入

输入的第一行包含一个整数 n (3 ≤ n ≤ 300) — 城堡多边形顶点的数量。

接下来的 n 行按逆时针顺序描述多边形顶点。其中第 i 个包含两个整数 xi 和 yi (|xi|, |yi| ≤ 104)——城堡第 i 个点的坐标。保证给定的点形成凸多边形,特别是它们中的任何三个点都不在同一条线上。

输出

在第一行中打印单个数字 r - 人员观看圈的最小半径。

在第二行中打印 Barney 应停留的点的坐标对。

在第三行中打印 Lyanna 应该停留的点的坐标对。

点应位于多边形内部。

坐标不能是整数。如果有多个答案,请打印其中任何一个。

如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。

示例

输入 #1

4
-41 67
-16 20
25 25
-36 85

输出 #1

0
-16 20
-36 85

输入 #2

7
-7 54
-5 31
-2 17
20 19
32 23
34 27
26 57

输出 #2

2.9342248
32.019503 23.0390067
-6.929116 54.006444

注意

在第一个示例中,人们可以呆在城堡的相对角落。