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

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2310 薔薇園の魔女

AOJ

二度と解きたくない

解法

全探索をします.
といっても直線を引く候補が無限個あるので,少し考察をします.

最適解の直線があったとして,分割する数を減らさないように少しずつ直線の角度をずらしていくと,直線とある格子点がぶつかるところで動かせなくなります.
このことを考えると,格子点を通る直線をほんのわずか左右に動かしたものだけを候補として考えればよく,HW本の直線だけ考えればいいことが分かります.
直線を決めたら,その直線が何回境界をまたぐかを求めてやるといくつに分割できるかが求められます.つまり直線と線分の交差判定ができればよいです.
サンプル2から,角をちょうど貫通する直線は角の生命体を分離しないっぽいです.いやこれどう見ても4つに分割してるでしょ...

あとはあとは線分と直線の交差判定をO(H+W)でやりたいので,直線を偏角ソートして順に探索していけばO(HW(H+W)で解けます.
探索上では格子点を通る直線の探索をしているので,格子点を通る場合は左右にずらした場合の線分の交差について,2通りのカウントが必要になります.