🌳

[ABC259 D] Circumferences

2024/03/03に公開

Ruby

隣接判定が難しい問題。

解き方

簡単に言えば、

隣接している円を連結する
二点が連結しているか確認する

とするだけだが、

円と円の隣接(正確には交差)判定
スタート地点とゴール地点に該当する円を探す

の二点でユークリッド距離の計算が必要になる。

驚きの工夫

スタート地点とゴール地点に対応する円を探すためには、隣接判定と似たような処理を再度書かねばならず、面倒である。この場合「半径0の円と見なす」というユーザー解説で紹介のアイデアを用いると、スタート地点とゴール地点に対応する円を探す処理がそもそも不要になる。

はまったところ

含まれる場合も隣接判定に含めてしまう

円周だけに道があるのだから円周と円周が接触していないといけなかった。

ノード値に座標を使ってしまう

これは盲点だった。同じ座標を持つ円が存在する場合に不整合が起きるので同じ座標の円であってもユニークにしないといけなかった。

平方根を求めてしまう

平方根まで求めていると TLE になる。本当の距離を知りたいわけではないので、相手を二乗して比較すればよい。これは小数の誤差を避ける意図もある。

Range 型を使ってしまう

a <= b && b <= c は (a..c).cover?(b) と書いてしまいがち。というか、むしろそう書くべきだと考えているが、もともと TLE 寸前なので確実に超えてしまう。

コード (AC)

N = gets.to_i
SX, SY, TX, TY = gets.split.collect(&:to_i)           # => [0, -2, 3, 3]
XYR = N.times.collect { gets.split.collect(&:to_i) }  # => [[0, 0, 2], [2, 0, 2], [2, 3, 1], [-3, 3, 3]]

Circle = Data.define(:id, :x, :y, :r) do
  def overlap?(o)
    length_sq = (o.x - x)**2 + (o.y - y)**2
    (o.r - r)**2 <= length_sq && length_sq <= (o.r + r)**2
  end
end

all = [[SX, SY, 0], *XYR, [TX, TY, 0]]
all = all.collect.with_index { |e, i| Circle[i, *e] }

ds = DisjointSet.new
all.combination(2) do |a, b|
  if a.overlap?(b)
    ds.unite(a.id, b.id)
  end
end
ans = ds.same?(all.first.id, all.last.id)             # => true
puts ans ? "Yes" : "No"

参考

https://atcoder.jp/contests/abc259/editorial/4302