KUPC2012 G.村

その他

問題

ある村にN個の家がある。これらの家は以下の条件を満たして存在している。

  • ある実数Rが存在
  • 2つの家の距離がR以下なら、同じ表札を持つ
  • 2つの家の距離が3R以上なら、違う表札を持つ
  • 任意の2つの家はR以下もしくは3R以上のいずれか

この村の表札の種類は全部で何種類か。

考え方

村をRxRのブロックに分解する。
同じブロックに存在する家は必ず同じ表札を持つ。
隣接ブロックの場合、最大でも2√2R<3Rなので、同じ表札を持つ。

R以下にしか家を持たないはずなので、同じ表札をもつグループの塊は、隣接ブロックの外側のブロックとは必ず隣接しない。

なので、N点について、ブロック単位で扱い、その数を数える。
ただし、8近傍隣接ブロックが存在するときは、答えに+1はしない。

bx=floor(x/R); by=floor(y/R);だと、誤差死してしまっていたので、bx=floor(x/R-EPS); by=floor(y/R-EPS);にして、境界上にある点をより値の小さいブロックに割り当てるようにしたら通った。

反省

部分点狙いで、線形探索で、近くに同じ表札の家がないか調べるコードを出して、線形の部分をO(log n)やO(√n)あたりにすればと思って、書こうと思ったけど、平面座標について、線形以下オーダーで探す方法がうまくかけず。
別解で平面走査でO(nlogn)があるので、書けるようにしたい。。。。