読者です 読者をやめる 読者になる 読者になる

(o_o)

ブログ。

AOJ2258 全自動円形掃除機™

全自動円形掃除機™ をACしたのはもう1年近く前だけど,いまさら解説記事を書きます.
いろんな実装方法はあるけど,自分の実装はこんな感じ.

多角形の各線分からR内側に平行移動した線分を列挙する
各頂点からの半径 R の円周を列挙する
これらの線分や円周の交点で線分や円を区切ってアレンジメントする
これらの線分や円弧から,多角形の外壁からの距離が R のものを列挙する
(線分や円弧からランダムに一点選び,多角形の各辺との距離の最小値をとればよい)
列挙した線分や円弧をつないで閉曲線にする
この閉曲線を境界とする閉領域の中からルンバ™の中心点を内部に含むものを選ぶ.
(この領域がルンバ™が到達可能な領域である.)
この閉曲線の各線分,円弧について,以下を行う
1. 線分を R だけ外側にずらす
2. 円弧は円と円弧の端を結ぶ 2 線分に変換する
3. こうしてできた新たな多角形について,内角が180度を超える角の外側を円弧で埋める
こうして生成した域がルンバ™が到達可能な領域である.

ジャッジ入力をビジュアライザにかけた結果は以下の通り.
赤い線分&円で囲まれてるのが求めたいやつ.
http://mars.kmc.gr.jp/~asi1024/roomba/problem
http://mars.kmc.gr.jp/~asi1024/roomba/answer
全体的にジャッジ入力が弱い.そもそも軸に平行な多角形しかない.
軸に平行な多角形しか入力にないことは入力の制約に書かれているらしいです.
だったらもっと簡単に解けそう・・・

ソースコードは省略