Processing math: 77%

[20210115专题选讲]Jewelry Size

一道水题,二分就做完了,就是有个情况有点坑。

题目大意

给定一圆内接多边形的边长 a1,,an,求该圆半径。

n1000ai[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,设 θiai 对应的圆心角(限制在 [π,π]),容易写出 θi=2asin(ai2r).

第一种情况:最大弦不为优弦。

显然若答案为 r0,则 iθi=2π.

容易知道 dθidr=2air4r2a2i<0,所以 diθidr<0,直接二分。

第二种情况:最大弦为优弦。

a1=max

显然若答案为 $r0,则 \theta_1-\sum\limits{i\ne 1}\theta_i=0$.

单调性感性理解:

如果将 a_2,\cdots,a_n 相邻地放置在圆上,则总弧所对的弦一定随着 r 的增大而增大。

——神仙 zz

具体证明不会。

代码

一定要搞清是单调递减还是递增!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#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);
}