CF 1C

Ancient Berland Circus

Description

给出一个正多边形的三个顶点坐标，输出该正多边形的最小面积是多少。

Solution

首先，我们需要先求出该正多边形的中心，可以根据三个点，两条中垂线来求交点，即为正多边形中心。方法如下：

求中垂线

point A: (x0, y0) point B: (x1, y1)

∵ 中垂线上的点到两点的距离相等
∴ 设 (x, y) 是中垂线上的点
则中垂线方程为 (x - x0)^2 + (y - y0)^2 = (x - x1)^2 + (y - y1)^2

化为一般式 2 * (x1 - x0) * x + 2 * (y1 - y0) * y + (x0 ^ 2 + y0 ^ 2 - x1 ^ 2 - y1 ^ 2) = 0

求两直线交点

line A: a0x + b0y + c0 = 0
line B: a1x + b1y + c1 = 0

联立方程

| a0x + b0y + c0 = 0
| a1x + b1y + c1 = 0

解得 x = (b1 · c0 - b0 · c1) / (a1 · b0 - a0 · b1)
y = (a1 · c0 - a0 · c1) / (a0 · b1 - a1 · b0)

(x, y) 即为两直线的交点

然后，我们可以用 atan2 函数，来求出从中心点到顶点的直线，进而求出每个角的大小。

假设所求多边形的边数为 n，求出的中心点为(x₀, y₀)因为每个角的度数为 2π / n，所以任意角度相减也是 2π / n 的倍数。由于 N 的取值范围不大，并且所求的是最小面积，我们便可以从小到大枚举 n 的值来找到符合条件的 n。代码如下：

• a_i = atan2(y_i - y₀, x_i - x₀)
• ΣΣ fabs(sin(n · (a_i - a_j) / 2)) == 0

上述最后一个公式用到一个技巧，就是 sin(x) == 0，则 x 为 π 的倍数。除此之外，判等的时候记得使用 fabs(x) < eps 来消除误差。

最后，知道边数 n 和边长 r² = (x_i - x₀)² + (y_i - y₀)²，面积公式为：

• S = 0.5 · sin(2·π/n) · n · r²