JAG夏合宿day1 E

まず円の面積を求めるのは簡単で多角形の面積を求められればよい。多角形の頂点と円までの距離が等しいという制約は多角形の頂点がある半径の円上に乗っていると考えることができる。ある半径rの円を考えたときにこの円上に多角形をつくることが可能かどうかには単調性があり二分探索を行うことができる。この二分探索の判定は多角形の中心角が360度になっているかを判定する。長さがr,r,l[i]の三角形であれば中心角は正弦定理から$2arcsin(l[i]/2r)$と求められる。各三角形について中心角を求め合計が360度より小さければrを小さくし、360度より大きければrを大きくする。

これで大体解くことができるが多角形が円の中心を含まない場合がコーナーケースになっている。もし円の中心を含まなければもっとも長い辺の角度は求めた中心角の反対側としなければならない。このように訂正した判定条件で二分探索を行うことで円の中心を含まない状況でも答えを求めることができる。

円の中心を含むかの判定を行うには取りうる最も短い半径で中心角の和を求めてこれが360度以下であれば円の中心を含まないと判定できる。

また半径rのときに実際に多角形の面積を求めるには$r^2sin(\text{中心角})/2$と求めることができる。

 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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98


#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using PII = pair<int, int>;
template <typename T> using V = vector<T>;
template <typename T> using VV = vector<V<T>>;
template <typename T> using VVV = vector<VV<T>>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll INF = (1LL<<60);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  const double PI = acos(-1);

  int t;
  cin >> t;
  REP(test, t) {
    double c;
    int n;
    cin >> c >> n;
    V<int> l(n);
    REP(i, n) cin >> l[i];
    sort(ALL(l));

    // 半径と弦の長さから中心角を求める
    auto ang = [&](double r, double len) {
      return 2*asin(len/2.0/r);
    };

    // 半径として取りうる最小を設定したときの中心角の合計
    // 半径を小さくする → 中心角が大きくなる = 最大の中心角の合計を求めている
    double ans = 0, sum = 0;
    for(auto i: l) sum += ang(l[n-1]/2.0, i);
    
    // 円の中心が多角形の内部に存在する
    if(sum > 2*PI) {
      // lbをこれより小さくすると三角不等式を満たさず三角形にならないため判定が狂う
      double lb = l[n-1]/2.0, ub = c;
      REP(i, 100) {
        double mid = (lb+ub)/2;
        sum = 0;
        for(auto i: l) sum += ang(mid, i);
        if(sum >= 2*PI) lb = mid;
        else ub = mid;
      }
      for(auto i: l) ans += lb*lb*sin(ang(lb,i))/2.0;
    }
    // 円の中心が多角形の外にある
    else {
      double lb = l[n-1]/2.0, ub = c;
      REP(i, 100) {
        double mid = (lb+ub)/2;
        sum = -ang(mid, l.back());
        REP(i, n-1) sum += ang(mid, l[i]);
        if(sum <= 0) lb = mid;
        else ub = mid;
      }
      for(auto i: l) ans += lb*lb*sin(ang(lb,i))/2.0;
      // 最も長い辺について余計に足している部分を引く
      ans -= lb*lb*sin(ang(lb,l[n-1]));
    }

    cout << fixed << setprecision(15) << c*c/4/PI - ans << endl;
  }

  return 0;
}

ferin blog

JAG夏合宿day1 E - Fences