ZOJ 3806 – Incircle and Circumcircle 解题报告

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

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

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

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

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

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

以及

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

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

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

当 2*r <= R 时,只需要找到一组 alpha 和 beta 就可以算出三角形三边长了。 经过分析,如果取 alpha = 2pi/3,那么当 beta 在 (0,2pi/3] 的范围内变化时,z 可以取遍 (0,1] 中的每一个数。 所以我定了 alpha=2pi/3,然后二分找出 beta,算出 gamma,三边就可以计算出来了。参考代码

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

发表评论

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