ARC 181 | F - Silver Woods

코드

#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;
}

참고 자료