← 返回题目列表

Codeforces · 772/B

B. 不稳定的风筝

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

给定一个凸多边形 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 的距离来使其成为非凸的。