ABC 251 G — Intersection of Polygons

考察

凸多角形を平行移動しても各辺の向きと内向き半平面の法線は変わらず、変わるのは半平面境界の右辺定数だけである。

採用する候補: 辺ごとに全平行移動の最強半平面を前計算

共通のN方向それぞれで右辺の最大値を取れば、M個の多角形の共通部分をN個の不等式だけで表せる。

棄却する候補: 各質問点をM個全ての多角形へ点包含判定

質問ごとにN M個の辺判定が必要となり、最大制約では過大になる。

反時計回りの辺ベクトルq_iに対し、点zが平行移動後の内部にある条件はcross(q_i,z)がその移動後頂点のcross値以上であることと書ける。

全ての移動多角形に入るには各方向の全不等式を満たす必要があり、同じ左辺に対する右辺の最大値だけを残せる。

各辺iについてM個の平行移動後頂点との外積定数を計算し、その最大値limit[i]を保存する。各質問点zについて全iでcross(edge[i],z)≥limit[i]かを調べ、全て満たせばYesとする。

典型の発動条件

凸多角形の半平面表現

発動条件: 点包含や複数凸集合の共通部分を辺ごとの線形不等式で扱いたい。

反時計回り各辺の内側条件を外積不等式として表す。

同一左辺の制約集約

発動条件: 多数の制約が法線を共有し定数項だけ異なる。

右辺の最大値だけを残し、平行な半平面の論理積を一つへ縮約する。

問題固有の要素

平行移動族では辺方向が共通なので、M個の多角形の共通部分も元と同じN方向の半平面だけで表現できる。

別の問題へ持ち帰る視点: 変換後も係数が不変で定数だけ動く制約群は、方向ごとの最厳値へ畳み込める。

正当性

反時計回りの辺e_iとその始点p_iに対し、移動u_j後の内側はcross(e_i,z)≥cross(e_i,p_i+u_j)。全移動で左辺が共通なので、各方向で右辺の最大limit_iを残すことは不等式の論理積と同値。N方向全ての条件を満たす点が全多角形の共通部分にある。空の共通部分も特別な多角形構築なしで自動的に判定できる。

実装上の注意

  • 座標差と平行移動を含む外積は64ビット整数で計算し、境界上は内部として等号を許す。頂点と対応する辺の向きを全箇所で統一する。

復習の核

  • M=1、移動量0、共通部分の境界上、共通部分が空になる例で、全多角形への素朴な包含判定と比較する。

計算量と制約

時間

O(N(M+Q))。

空間

O(N)補助領域。入力を保持するならO(N+M+Q)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 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_i, y_i \leq 10^8; -10^8 \leq u_i, v_i \leq 10^8; -10^8 \leq a_i, b_i \leq 10^8; All values in input are integers.; (x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N) forms a convex N-gon in the counterclockwise order.; Each interior angle of the polygon P is less than 180 degrees.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Intersection of Polygons の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 半平面制約・凸領域の共通部分

主題
  • 半平面制約・凸領域の共通部分: 凸多角形を向き付き辺の線形半平面制約へ変換し、平行移動後も左辺が同じ制約を最強の右辺へ集約して共通部分への包含を判定できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 半平面制約・凸領域の共通部分

      執筆: abc-explanation-author1.1.1 / revision 1

      学習の位置

      体系上の位置: 半平面制約・凸領域の共通部分

      • 凸多角形を向き付き辺の線形半平面制約へ変換し、平行移動後も左辺が同じ制約を最強の右辺へ集約して共通部分への包含を判定できる。

      先に読む単元:

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題