No.96

No.94 の制限が厳しいバージョンである.

10km以内の中継局間に辺があるグラフを想定し. Union-Find でグループ分けして, グループごとの中継点間の最長距離を求めるという基本方針は変わらない.

ただし, 愚直に実装すると Union-Find もグループごとの最長距離を求めるのも $O(N^2)$ の計算量なので間に合わない.

そこで, 空間を大きさ $10 \times 10$ のマスで分割して中継局をこのマスでグループ分けする. ある中継局と10km以内の距離にある中継局は, ある中継局があるマスとその隣接8マスにしか存在しないので, Union-Find の計算量を減らすことができる.

次に Union-Find グループ分けしたグループごとの中継点間の最長距離であるが, これを満たす中継点はグループ内の中継点の凸包上にあるので, 凸包を計算すれば対象の中継点を減らすことができる.