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

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

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

AOJ2442 ConvexCut

AOJ

間違えてこっちの問題を解いて満足していたけどマヨ子さんのブログを見て違うことに気が付いた
凸多角形の切断 | 計算幾何学 | Aizu Online Judge


解法

点Pが多角形に存在するとします.
多角形を点Pを通る2つの直線で4分割し,分割後の図形をA,B,C,Dとすると,
面積について考えたとき,A+B=C+D,A+C=B+Dが成り立つので,
これらを整理して計算すると,対角の要素A,CB,Dについて,A=CおよびB=Dであることがわかります.

f:id:NitCoder000:20160705154119p:plain
このことから,二つの直線の間を狭めていくと,
図形は点対称でなければならないことが分かるので.
図形が点対称であるかどうかを求めてやるだけで答えがわかります.