A-Ju 有一座华丽的城堡,她经常喜欢住在里面。然而,她厌倦了在城堡里生活太久。因此,她决定将她的城堡重建成某种特定的形状,让她的城堡更加美丽。
假设我们将 A-Ju 的城堡表示为 2D 平面上的 2D 凸多边形$$$^{\text{*}}$$$。阿菊的目标是将她的城堡重建为点对称凸多边形。这里,如果存在中心$$$c$$$,则多边形是点对称的,使得对于多边形中的每个点$$$p$$$,$$$p$$$在$$$c$$$上的反射$$$p^\prime$$$也在多边形中。
虽然设计任意点对称凸多边形形状很容易,但重建成本非常高。经过一番估算,阿菊发现重建的成本与原城堡和新城堡对称差$$$^{\text{†}}$$$的面积成正比。示例如下图所示:
在上面的示例中,A-Ju 的城堡是由点 $$$(3, 7) - (2, 1) - (6, 3)$$$ 形成的凸多边形形状。将她的城堡重建为 $$$(3, 7) - (\frac{7}{3}, 3) - (\frac{13}{3}, \frac{1}{3}) - (5, \frac{13}{3})$$$ 形成的多边形形状后,这两个多边形之间的对称差异面积将为 $$$\frac{11}{3}$$$。差异可以计算为附加面积(由绿色网格区域表示)和剃须面积(由红线区域表示)之和。
请编写一个程序,帮助阿菊设计新城堡的蓝图,使原城堡和新城堡之间的对称差异面积最小。你只需要输出最小值,因为 A-Ju 要先估算她的成本。
输入
第一行包含一个整数$$$n$$$,表示构成A-Ju的城堡的多边形的顶点数。
接下来是$$$n$$$行,其中第$$$i$$$行包含两个整数$$$x_i、y_i$$$,表示第$$$i$$$个顶点的坐标。顶点按逆时针顺序给出。
- $$$3\leq n\leq 500$$$
- $$$|x_i|, |y_i|\leq 10^4$$$
- 顶点按逆时针顺序给出,并保证形成没有三个共线点的凸多边形。
输出
在一行中打印一个实数,表示原城堡和新城堡之间对称差的最小面积。
如果绝对或相对误差不超过 $$$10^{-4}$$$,您的答案将被接受。正式来说,让您的答案为$$$a$$$,陪审团的答案为$$$b$$$。如果 $$$\frac{|a-b|}{\max(1,|b|)}\le 10^{-4}$$$,则认为您的答案是正确的。
示例
输入 #1
3 2 1 6 3 3 7
输出 #1
3.666666666667
输入 #2
4 0 0 5 0 5 5 0 5
输出 #2
0.000000000000