square869120Contest #5: B - Emblem

問題

B - Emblem

解説

円が包含したり重なったりしてはいけないので、自由に決められる円の半径は、そのうちの最小値に合わせて良い。そのような半径を最大化するためには、二分探索を用いればよい。

また、円が交差しないような条件は、2円の中心間の距離と半径の和から導くことができる。

他、のコーナーケースはサンプルが示してくれている。

因みに、doubleの二分探索だから境界条件適当でいいだろうと思って、以下のintersectの関数で等号をつけていたらWAだった。原因は不明だが、複数の円同士の重なり合いを考慮すると誤差以内に収まらなくなるのかもしれない？

struct circle {
  double x, y, r;
};

int N, M;
vector<circle> fixedc;
vector<circle> arbit;

bool intersect(circle const& a, circle const& b) {
  return sqrt(pow(abs(a.x - b.x), 2.0) + pow(abs(a.y - b.y), 2.0)) < a.r + b.r;
}

bool intersection_exists() {
  auto allc = fixedc;
  for (auto c: arbit) allc.push_back(c);
  rep(i, allc.size()) REP(j, i + 1, allc.size()) {
    if (intersect(allc[i], allc[j])) { return true; }
  }
  return false;
}

double solve() {
  double l = 0, r = 100001;
  rep(_, 100) {
    auto m = (l + r) / 2;
    rep(i, M) {
      auto a = arbit[i];
      arbit[i] = {a.x, a.y, m};
    }
    if (intersection_exists()) {
      r = m;
    } else {
      l = m;
    }
  }
  return (l + r) / 2.0;
}

int main() {
  cin >> N >> M;
  rep(i, N) {
    double x, y, r; cin >> x >> y >> r;
    fixedc.push_back({x, y, r});
  }
  rep(i, M) {
    double x, y; cin >> x >> y;
    arbit.push_back({x, y, 0.0});
  }

  if (M == 0) {
    double min = 1e10;
    rep(i, N) {
      minimize(min, fixedc[i].r);
    }
    printf("%.15f\n", min);
    return 0;
  }

  printf("%.15f\n", solve());
}