Description

对于某个区域的中心点的计算方法，目前并没有公认的标准。这一事实常常被用来宣传不同的地方。你总能找到一种“中心”的定义方式，使得你的城市成为国家的中心！Gloria 决定制定一个通用的标准，并找到真正的中心。

考虑一个凸多边形内部的任意一点，以及任意一个方向。存在唯一一条经过该点、与该方向平行、且两端都在多边形边界上的线段。该点将这条线段分成两部分。定义该方向下的“不平衡度”为较长部分长度与较短部分长度的比值。该点的“不平衡度”定义为所有方向下最大的不平衡度。

Gloria 对这个值很感兴趣，并希望将凸多边形内不平衡度最小的点定义为该多边形的“Grand center”。请你帮她计算给定多边形的 Grand center 的不平衡度。

Input Format

第一行包含一个整数 $n$，表示给定凸多边形的顶点数（$3 \le n \le 10\,000$）。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个顶点的坐标（$-10^5 \le x_i, y_i \le 10^5$）。$x$ 轴从左到右，$y$ 轴从下到上。顶点按逆时针顺序给出。该多边形是严格凸的：所有内角都严格小于 $\pi$。

Output Format

输出一个实数，表示该多边形 Grand center 的不平衡度。若你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

4
0 0
1 0
1 1
0 1

1

3
0 0
1 0
0 1

2

4
0 0
2 0
4 4
0 2

1.5

Hint

下图展示了三个样例测试的情况：

在第一个样例中，对于正方形的中心点，任意方向下的不平衡度均为 $1$，即任意线段都被平分。

在第二个样例中，众所周知，三角形的中线交点将中线分成 $2:1$ 的比例。在给定的三角形中，中线方向对应该点最大的不平衡度。对于其他点，不平衡度会更大。

在第三个样例中，Grand center 位于 $(1.6, 1.6)$。

由 ChatGPT 4.1 翻译