一道水题,二分就做完了,就是有个情况有点坑。
题目大意
给定一圆内接多边形的边长 a1,⋯,an,求该圆半径。
n≤1000,ai∈[1,6000]∩\Z。
source: ICPC Asia Regional Contest, Yokohama, 2021–03–17, Problem E
link: http://qoj.ac/contest/802/problem/2267
思路
二分 r 即可。
考虑在半径为 r 的圆上放置弦 ai,设 θi 为 ai 对应的圆心角(限制在 [−π,π]),容易写出 θi=2asin(ai2r).
第一种情况:最大弦不为优弦。
显然若答案为 r0,则 ∑iθi=2π.
容易知道 dθidr=−2air√4r2−a2i<0,所以 d∑iθidr<0,直接二分。
第二种情况:最大弦为优弦。
令 a1=max
显然若答案为 $r0,则 \theta_1-\sum\limits{i\ne 1}\theta_i=0$.
单调性感性理解:
如果将 a_2,\cdots,a_n 相邻地放置在圆上,则总弧所对的弦一定随着 r 的增大而增大。
——神仙 zz
具体证明不会。
代码
一定要搞清是单调递减还是递增!
1 |
|