[20210115专题选讲]Jewelry Size

Posted on | In ,

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

题目大意

给定一圆内接多边形的边长 $a_1,\cdots,a_n$，求该圆半径。

$n\le 1000$，$a_i\in [1,6000]\cap \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}$

显然若答案为 $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);
}