AOJ 1283 : Most Distant Point from the Sea

幾何

問題↓

Most Distant Point from the Sea | Aizu Online Judge

問題概要

  • 凸多角形が反時計回りで与えられます。
  • 凸多角形の内部にある点のうち
    辺からの距離が最も遠い点との距離を出力してください。

解法

  • 辺からの距離をDとしてそこから多角形の内部に距離Dだけ並行移動した直線で凸多角形を切る。
  • 全ての辺に対してその動作を行った時、凸多角形が残っていれば
    どの辺からも距離Dだけ離れた点が存在することが分かる。
  • 直線で凸多角形を切る動作はconvex_cutを使ってO(N)でで切る。
ソースコード

感想

convex_cutを初めて有用活用した。

ぶっちゃけ解法全くわからんかった、初見でこんなのありかよとか思ったが教育的に良い問題だ。

線分の平行移動とか短いけどライブラリ化すると楽そうだ。