给定一个凸多边形 P,它有 n 个不同的顶点 p1、p2、...、pn。顶点 pi 在 2D 平面中具有坐标 (xi, yi)。这些顶点按顺时针顺序列出。
您可以选择一个实数 D,并将多边形的每个顶点从其原始位置移动最多 D 的距离。
找到 D 的最大值,使得无论您如何移动顶点,多边形都不会与自身相交并保持凸形。
输入
第一行有一个整数 n (4 ≤ n ≤ 1 000) — 顶点数。
接下来的 n 行包含顶点的坐标。第 i 行包含两个整数 xi 和 yi (- 109 ≤ xi, yi ≤ 109)——第 i 个顶点的坐标。这些点保证按顺时针顺序给出,并将形成严格的凸多边形(特别是,没有三个连续的点位于同一条直线上)。
输出
打印一个实数 D,它是无论您如何移动顶点,多边形都保持凸形的最大实数。
如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。
也就是说,我们假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。
示例
输入 #1
4 0 0 0 1 1 1 1 0
输出 #1
0.3535533906
输入 #2
6 5 0 10 0 12 -4 10 -8 5 -8 3 -4
输出 #2
1.0000000000
注意
这是第一个样本的图片
这是使多边形非凸的示例。
这不是一个最佳解决方案,因为我们移动一个点的最大距离是 ≈ 0.4242640687,而我们可以通过仅将每个点移动最多 ≈ 0.3535533906 的距离来使其成为非凸的。