Codeforces Round #339 (Div. 1) A. Peter and Snow Blower

※問題をエスパーしたので問題を勘違いしています。

点P と多角形 S が与えられる。点 P を中心とした円を 2 つ描き、多角形 S がその円の間に挟まれるようにする。この 2 つの円に囲まれる領域の面積の最小値を求めよ。

点と多角形の距離の最小値・最大値を求めれば面積の最小値が求められる。

点と多角形の距離の最小値は、点と多角形のそれぞれの辺の距離の最小値になる。そのため、点と線分の距離を求めたい。

点と線分の距離は、点が緑色の領域内部にあるかどうかで求め方が変わる。

f:id:pekempey:20160115173213p:plain

以降、直線の単位方向ベクトルを $d=(q-p)/|q-p|$ とする。

図でいうと r1 がこのケースになる。これは点と直線の距離を求めればいい。点と直線の距離は外積を用いて、

$$ | d \times (r-p) | $$

で求められる。

図でいうと r2, r3 がこのケースになる。これは点と線分の端点の距離を求めればいい。点と点の距離は、

$$ |r-p| $$

で求められる。

上記の場合分けで求まるのは分かったが、緑色の領域に含まれるかどうかの判定はどのようにやればいいだろうか。これは簡単で、直線 PQ への r1 の射影をとって、それが線分 PQ 上にあるかどうかを見ればいい。つまり、

$$0 \le d \cdot (r-p) \le |q-p|$$

なら内部にある。

幾何の問題は複素数を使うと実装が軽くなる。複素数を使った基本的な幾何の操作を簡単にまとめておく。

Div1Aにしては簡単。