[20220115专题选讲] Jewelry Size
题目大意
给定一圆内接多边形的边长 \(a_1,\cdots,a_n\)，求该圆半径。
\(n\le 1000\)，\(a_i\in [1,6000]\cap \mathbb{Z}\)。
source: ICPC Asia Regional Contest, Yokohama, 2021–03–17, Problem E
link: http://qoj.ac/contest/802/problem/2267
思路
二分 \(r\) 即可。
考虑在半径为 \(r\) 的圆上放置弦 \(a_i\)，设 \(\theta_i\) 为 \(a_i\) 对应的圆心角（限制在 \([-\pi,\pi]\)），容易写出 \(\theta_i=2\operatorname{asin}(\dfrac {a_i}{2r})\).
第一种情况：最大弦不为优弦。
显然若答案为 \(r_0\)，则 \(\sum\limits_i\theta_i=2\pi\).
容易知道 \(\dfrac{ {\mathrm{d}}\theta_i}{ {\mathrm{d}}r}=-\dfrac{2a_i}{r\sqrt{4r^2-a_i^2}}<0\)，所以 \(\dfrac{ {\mathrm{d}}\sum\limits_i\theta_i}{ {\mathrm{d}}r}<0\)，直接二分。
第二种情况：最大弦为优弦。
令 \(a_1=\max\{a_i\}\)
显然若答案为 \(r_0\)，则 \(\theta_1-\sum\limits_{i\ne 1}\theta_i=0\).
单调性感性理解：
如果将 \(a_2,\cdots,a_n\) 相邻地放置在圆上，则总弧所对的弦一定随着 \(r\) 的增大而增大。
——神仙 zz
具体证明不会。
代码
一定要搞清是单调递减还是递增！
#include <cstdio>
#include <cmath>
#include <algorithm>
namespace mirai {
constexpr int MAXN = 1005;
constexpr long double PI = 3.14159265358979323846;
long double a[MAXN];
int main(int argc, char** argv) {
// std::freopen("ala.out", "r", stdin);
int n;
std::scanf("%d", &n);
for (int i = 0; i < n; ++i) {
std::scanf("%Lf", &a[i]);
if (a[i] > a[0]) {
std::swap(a[i], a[0]);
}
}
long double rl = a[0] / 2, rr = 1e9;
auto f1 = [=](long double radius) -> long double {
long double theta = 0;
for (int i = 0; i < n; ++i) {
theta += 2 * std::asin(a[i] / (radius * 2));
}
return theta;
};
while (rr - rl >= 5e-8) {
long double mid = (rl + rr) / 2;
// std::printf("%.10Lf %.10Lf %.10Lf\n", rl, rr, f1(mid));
if (f1(mid) > 2 * PI) {
rl = mid;
} else {
rr = mid;
}
}
long double ans1 = (rl + rr) / 2;
if (std::abs(f1(ans1) - 2 * PI) <= 5e-7) {
std::printf("%.10Lf\n", ans1);
return 0;
}
rl = a[0] / 2;
rr = 1e9;
auto f2 = [=](long double radius) -> long double {
long double theta = 2 * std::asin(a[0] / (radius * 2));
for (int i = 1; i < n; ++i) {
theta -= 2 * std::asin(a[i] / (radius * 2));
}
return theta;
};
// std::puts("---------------------------");
int cnt = 0;
while (rr - rl >= 5e-8) {
++cnt;
if (cnt == 100) {
break;
}
long double mid = (rl + rr) / 2;
// std::printf("%.10Lf %.10Lf %.10Lf\n", rl, rr, f2(mid));
if (f2(mid) < 0) {
rr = mid;
} else {
rl = mid;
}
}
std::printf("%.10Lf\n", (rl + rr) / 2);
return 0;
}
}
int main(int argc, char** argv) {
return mirai::main(argc, argv);
}