Zenn
😽

ARC 181 | F - Silver Woods

2020/11/03に公開
競プロ
二分探索
最小全域木
tech

問題

https://atcoder.jp/contests/abc181/tasks/abc181_f

考えたこと

半径rの円をy=-100からy=100の間を移動させる。その間に釘がある。以下のような図である。

半径rの円が通れるかどうかは以下のように緑で囲んだように、点と点の間が半径rより小さい点の集合に上下の直線との最短地点の点であるstartとgoalをそれぞれ足して、startからgoalまでの最長距離の\frac{1}{2}が円が通れる最大の半径である。

最小のrはr \ (0 < r \leq 100)の実数なのでひとつひとつ確かめることはできない。ただ範囲が決まっているのでこの範囲で二分探索を行いrが条件を満たすか試せばいい。

コード

実装はそんなに難しくない。

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  ll n;
  cin >> n;
  vector<vector<ld>> p(n, vector<ld>(2));  // (x, y)の配列
  for (int i = 0; i < n; i++) {
    cin >> p[i][0] >> p[i][1];
  }
  vector<pair<ld, vector<int>>> d;  // (d, (i, j)): dはp[i],p[j]間の距離
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      ld v = sqrt(pow(p[i][0] - p[j][0], 2) + pow(p[i][1] - p[j][1], 2));
      d.push_back({v, {i, j}});
    }
  }
  sort(d.begin(), d.end());

  ld left = 0;
  ld right = 200;  // 直径の最大
  ld cnt = 100;
  while (cnt > 0) {
    // 二分探索
    ld mid = (left + right) / 2;
    dsu uf(n);
    for (int i = 0; i < d.size(); i++) {
      if (mid < d[i].first) {
        break;
      }
      // 線分をつなげる
      uf.merge(d[i].second[0], d[i].second[1]);
    }
    // グループごとにy=-100とy=100との最小距離を確認してそれがmidより小さかったら通れない
    bool possible = true;
    for (auto group : uf.groups()) {
      ld minY = 100;
      ld maxY = -100;
      for (int i : group) {
        minY = min(minY, p[i][1]);
        maxY = max(maxY, p[i][1]);
      }
      if (abs(-100 - minY) < mid && abs(100 - maxY) < mid) {
        possible = false;
      }
    }
    if (possible) {
      left = mid;
    } else {
      right = mid;
    }
    cnt--;
  }
  cout << fixed << std::setprecision(12);
  cout << left / 2 << endl;
}

参考

Discussion