AtCoder Beginner Contest 251 G問題 Intersection of Polygons

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

座標平面上に凸 $N$ 角形 $P$ がある. この $P$ はの頂点は反時計回りに $p_1=(x_1, y_1), \dots, p_N=(x_N, y_N)$ である.

$M$ 個の凸 $N$ 角形 $P_1, \dots, P_M$ がある. このとき, $P_i$ は $P$ を $x$ 軸正の向きに $u_i$ , $y$ 軸正の向きに $v_i$ だけ平行移動して得られる凸 $N$ 角形である.

次の $Q$ 個の質問 $q$ に答えよ.

質問 $q$ : 座標平面上の点 $(a_q, b_q)$ は全ての $P_1, \dots, P_M$ に対して, その内部 (頂点, 辺含む) か?

制約

$3 \leq N \leq 50$
$1 \leq M \leq 2 \times 10^5$
$1 \leq Q \leq 2 \times 10^5$
$-10^8 \leq x_j, y_j, u_i, v_i, a_q, b_q \leq 10^8$
$P$ は凸 $N$ 角形である.

解法

この解法では次の事実を用いている.

実数 $A, B_1,\dots, B_M$ に対して, 以下は同値である.

$i=1,2, \dots, M$ に対して, $A \geq B_i$
$\displaystyle A \geq \max_{i=1,2, \dots, M} B_i$

以降では座標平面上の点と原点に対する位置ベクトルを同一視する. また, $P_i$ の内部 (と辺と頂点の和集合) を再び $P_i$ と書くことにする. そして, $x_{N+1}=x_1, y_{N+1}=y_1$ とし, $i=1,2, \dots, M, j=1,2, \dots, N+1$ に対して, $(q_{i,j}, r_{i,j})$ で $P_i$ の $j$ 番目の頂点の座標とする. つまり.

$q_{i,j}=u_i+x_j, \quad r_{i,j}=v_i+y_j$

である.

まず, 点 $(a,b)$ が凸 $N$ 角形 $P_i$ の内部 (頂点, 辺) であるための必要十分条件を考える. $P_i$ は $j=1,2, \dots, N$ における点 $(p_{i,j}, q_{i,j}), (p_{i,j+1}, q_{i,j+1})$ を通る $N$ 本の直線の分割によって表現できる. 特に, $P$ の頂点は反時計回りで与えられていることから, 以下は全て同値になる.

$(a,b) \in P_i$
任意の $j=1,2, \dots, N$ に対して, $(q_{i,j}, r_{i,j})$ から $(q_{i,j+1}, r_{i,j+1})$ への有向線分の左側にある.
任意の $j=1,2, \dots, N$ に対して, $\overrightarrow{(q_{i,j}, r_{i,j}) (q_{i,j+1}, r_{i,j+1})} \times \overrightarrow{(q_{i,j}, r_{i,j}) (a,b)} \geq 0$

となる. なお, 2つの平面ベクトル $u,v$ に対して, $u \times v$ で $u,v$ のクロス積を表すとする. ここで,

$\begin{align} \overrightarrow{(q_{i,j}, r_{i,j}) (q_{i,j+1}, r_{i,j+1})} &=(q_{i,j+1}, r_{i,j+1})-(q_{i,j}, r_{i,j}) \\ &=(q_{i,j+1}-q_{i,j}, r_{i,j+1}-r_{i,j}) \\ &=( (u_i+x_{j+1})-(u_i+x_j), (v_i+y_{j+1})-(v_i+y_j) )\\ &=(x_{j+1}-x_j, y_{j+1}-y_j) \end{align}$

であり, $i$ にはよらず, $j$ にのみによって決定される. よって, $v_j:=(x_{j+1}-x_j, y_{j+1}-y_j)$ とすると,

$\begin{align} &\phantom{\Leftrightarrow} \forall j=1,2, \dots, N; v_j \times \overrightarrow{(q_{i,j}, r_{i,j}) (a,b)} \geq 0\\ & \Leftrightarrow \forall j=1,2, \dots, N; v_j \times (a,b) \geq v_j \times (q_{i,j}, r_{i,j}) \\ \end{align}$

である.

今, $P_i$ に関する条件を調べたので, 最後にこれを動かすことにより,

$\begin{align} &\phantom{\Leftrightarrow} \forall i; (a,b) \in P_i \\ & \Leftrightarrow \forall i ; (\forall j; v_j \times (a,b) \geq v_j \times (q_{i,j}, r_{i,j}) ) \\ & \Leftrightarrow \forall i , \forall j; v_j \times (a,b) \geq v_j \times (q_{i,j}, r_{i,j}) \\ & \Leftrightarrow \forall j ; (\forall i; v_j \times (a,b) \geq v_j \times (q_{i,j}, r_{i,j}) ) \\ & \Leftrightarrow \forall j ; v_j \times (a,b) \geq \max_{i=1,2, \dots, M} (v_j \times (q_{i,j}, r_{i,j}) ) \\ \end{align}$