AOJ 2682 : Polygon Guards

Polygon Guards | Aizu Online Judge

問題概要

• 単純多角形が与えられます。
• 頂点を幾つか選び人を配置することで全ての頂点を監視したいです。
• 頂点Aに人を置いた場合に監視できる頂点Bの条件は、"線分A-Bが単純多角形の内部に完全に内包されている"
• 頂点数 <= 40

解法

• とりあいず各頂点について、人を配置するとどの頂点を監視できるかの情報をまとめる。
• 線分が単純多角形の内部に完全に内包されているかどうかは
  線分と多角形の辺の交点を全列挙してそれらをソートする。
  ソートした交点の隣
  り合う点同士の中心点が多角形の内包されているかを判定すればよい。（以下の黄色い点について内包判定する）
  

  

• 次にこういうのを解きたい
  
• あまりにも分からなくて進展がないので呟く

• 二部グラフが出来てA側の頂点を全てカバーするために必要なB側の頂点を最小にしたいみたいな問題になってしまったときどうしたらいいのかわからない pic.twitter.com/AGqoEqlaUG

  — さて (@public_sate) 2016年4月12日
  

• 強い人から回答が得られる。（ありがとうございます！）

• @public_sate NP-complete に見えます: https://t.co/zfPPEkldxm

  — みさわ (@Mi_Sawa) 2016年4月12日

• @public_sate それフローじゃ解けないタイプのやつなはずでグラフ特有の性質見てgreedyとかになるイメージ

  — 将来に対する漠然とした不安 (@DEGwer3456) 2016年4月12日

• NP完全な問題であることとグラフの性質見てgreedyという大ヒントが得られたので考えなおす。
• とりあいず頂点の被覆にかぶりがあるようなものを省く、すると考慮すべき頂点数が多くても30くらいに減る。（問題の性質的に割りとかぶるとこあるだろうと思い実行、これわりと結果論）
• ある頂点に人を置くと少なくとも4つの頂点は見れるので人を置く数は少なくともN/4でOK、つまり最大でも10人おけば良さそう。
• 30C10 = 30,045,015
• 選ぶ人数を少ない順に見ていけばいけそう。

ソースコード

感想

Degwer氏とMisawa氏に圧倒的感謝

前にもコンテストで最小支配集合に帰着してしまってどうしようもなかったことがあったので、其の場合のアプローチ方法がなんとなく分かったような気がする。