ZOJ 3806 – Incircle and Circumcircle 解题报告

这是我写的第一篇解题报告,在此有必要说明一下为什么决定写这一篇解题报告。

这道题是我在集训队 Div.2 训练赛中第一次做出的一道全场只有唯一一个人过的题,也是我过的第一道防 ak 题。就想写个解题报告纪念一下。题目很简单,希望大佬们不要嘲笑我。

题意是这样的,给出三角形的内切圆半径 r 和外接圆半径 R,判断是否存在可能的三角形三边长并输出。

这题能过也有运气成分,主要是在思考的时候突然想到了用角度来算边。

我的想法是这样的,记 O 为三角形的外心,连接 OA, OB, OC,三个圆心角分别记为 \alpha, \beta, \gamma,于是就有

S = {1 \over 2}R^2(\sin\alpha+\sin\beta+\sin\gamma)

这个公式当 \alpha > \pi 的时候也是成立的。
同时还有

S = {1 \over 2}(a + b + c)r

以及

\begin{aligned} a &= 2R\sin\frac{\alpha}{2} \\ b &= 2R\sin\frac{\beta}{2} \\ c &= 2R\sin\frac{\gamma}{2} \end{aligned}

联立上述各式和 \alpha+\beta+\gamma=2\pi 就可以得到

z = {2r \over R} = \frac{\sin\alpha+\sin\beta-\sin(\alpha+\beta)}{\sin\frac{\alpha}{2}+\sin\frac{\beta}{2}+\sin\frac{\alpha+\beta}{2}}

我们来分析 z 的值域,在 (0,\pi) 内令

{\partial z \over \partial \alpha} = {\partial z \over \partial \beta} = 0

得到当 \alpha = \beta = {2\pi \over 3} 的时候 z 有极大值 1,所以我们得到当 2r > R 时是无解的。

2r \le R 时,只需要找到一组 \alpha\beta 就可以算出三角形三边长了。
经过分析,如果取 \alpha = {2\pi \over 3},那么当 \beta(0,{2\pi\over{3}}] 的范围内变化时,z 可以取遍 (0,1] 中的每一个数。

所以我定了 \alpha={2\pi\over{3}},然后二分找出 \beta,算出 \gamma,三边就可以计算出来了。参考代码

作者:
孑枵 Abreto版权所有,转载时必须以链接形式注明作者和原始出处及本声明,本站有权追究其法律责任。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据