巴尼终于找到了那个人,一位名叫莱安娜的美丽的年轻女士。问题是,莱安娜和巴尼被困在洛斯勋爵的城堡里。这座城堡的形状是 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
注意
在第一个示例中,人们可以呆在城堡的相对角落。