题解 CF1C 【Ancient Berland Circus】

· · 题解

为什么 CF 的题面都这么磨叽 一句话了事啊

这题面翻译成人话就是“求一个面积最小的正多边形来涵盖给定的三个点”。经过分析，这个正多边形的外接圆一定就是给定的三点构成的三角形的外接圆。

海伦公式是几何里最基础的公式了，令 p 为 \triangle ABC 的半周长，三角形三边长分别为 a,b,c，那么有：

S_{\triangle ABC}=\sqrt{p(p-a)(p-b)(p-c)}

海伦公式推导过程戳这里，由于不是本题解的主要内容，故此不放具体推导。

易知若三角形三边长分别为 a,b,c，那么 S_{\triangle ABC}=\dfrac 1 2 ab\sin C，推导过程如下：

\text{令} \triangle ABC\ a\ \text{边上的高}\ AD\ \text{为}\ h, S_{\triangle ABC}=\dfrac 1 2ah \because Rt_{\triangle ADC} \therefore h=b\ \cdot\ \sin\angle C \therefore S_{\triangle ABC}=\dfrac 1 2ab\sin C

又有正弦定理：

\dfrac a {\sin A}=\dfrac b {\sin B}=\dfrac c {\sin C}=2R

可得：

R=\dfrac{abc}{4S_{\triangle ABC}}

推导过程：

\because\dfrac{c}{\sin C}=2R \therefore S_{\triangle ABC}=\dfrac 1 2ab\sin C=\dfrac {abc}{4R} \therefore R=\dfrac{abc}{4S_{\triangle ABC}}

这样我们就可以利用余弦定理和反三角函数计算出三角形的三条弦所对的圆心角的度数。

显而易见的结论是，三条弦所对的圆心角度数的最大公约数 \alpha 就是正多边形的中心角。

中心角指的是正多边形相邻两顶点与其中心连线的夹角。正 n 边形中心角的度数是

\alpha=\dfrac{360\degree}{n}

接下来我们就能推导出正多边形的面积：

S=\dfrac{\pi R^2\sin \alpha}{\alpha}

推导过程比较复杂，需要认真消化。同时，三角函数一定要学明白。

详细代码这里就不给出了，只是给一个对 double 类型做 \gcd 的模板函数：

double gcd(double x, double y) {
    while (fabs(x) > eps && fabs(y) > eps) {
        if (x > y)
                x -= floor(x / y) * y;
        else
                y -= floor(y / x) * x;
    }
    return x + y;
}

同时也有 \gcd_{a,b,c}=\gcd_{\gcd_{a,b},c}

完结撒花~ 求赞求互关QAQ