幾何の基本判定と座標変換
概要
幾何の基本判定・配置・座標変換
交差・方向・距離・接触条件を、外積、端点順、格子占有または変換後座標の局所判定にする。
考え方
向きは二つのベクトルの外積、角度の大小は半平面と外積、射影は内積で表す。向きの符号から交差条件を導けば、atan2や平方根を使わず幾何条件を比較できる。平行・共線は別の境界として扱う。
平面ベクトルa=(a_x,a_y),bについてcross(a,b)=a_x b_y−a_y b_x、dot(a,b)=a_x b_x+a_y b_y。三点P,Q,Rの向きはcross(Q−P,R−P)の符号で、正なら反時計回り、0なら共線となる。
閉線分PQとRSの交差は、R,Sが直線PQの同じ側に厳密にはなく、P,Qも直線RSの同じ側に厳密にはないことに、x,y両軸のbounding intervalが重なる条件を加えて判定する。符号の積を使わず符号比較すればさらに大きい積を作らず済む。共線では前者だけが常に真なので後者が重なりを決め、長さ0の線分と端点接触も含められる。
非零ベクトルの偏角sortは、上半平面(y>0またはy=0,x≥0)を先にし、同じ半平面ではcross(a,b)>0をa<bとする。同方向を区別するなら長さやIDでtieを決める。原点ベクトルは角度が未定義なので先に分ける。射影の係数はdot(X−P,Q−P)/dot(Q−P,Q−P)で、線分への最近点なら[0,1]へclampする。P=Qは点との距離で処理する。距離の大小だけなら二乗を使える。
座標u=x+y,v=x−yでは |Δx|+|Δy|=max(|Δu|,|Δv|)。符号が同じ場合は和、異なる場合は差の絶対値が左辺になることから証明できる。逆変換x=(u+v)/2,y=(u−v)/2に戻す際はu,vのparityが同じという整数格子条件も残す。
射影で落とした座標も検査する
3D直線を平面へ射影して得た交点は、元の交点の候補に過ぎない。二直線の残りの座標が違えば、ねじれの位置である。また射影した二直線が重なっていても、3Dでは平行な場合と一点で交わる場合がある。射影の退化を分け、元の全座標の式を同時に確認する。
方向のx成分が非零なら、直線はy=ax+b,z=cx+dで一意に表せる。有理数の分母を正、分子・分母を互いに素、0を0/1にして、四係数を一致判定のキーにできる。二直線のaが違えばyの式からxを求めzを確認、aが同じでcが違えばzからxを求めyを確認する。両傾きが同じなら切片も同じ場合だけ一致、違えば平行である。ABC301 Gでは有効な全直線がこの条件を満たすので、交点の有理数キーまで具体化できる。一般の3D直線でx成分が0なら、別の媒介座標またはベクトルによる式が必要となる。
成立条件と計算量
一つの判定は固定長の算術ならO(1)。座標の最大値から外積の型を選び、差を取る前のoverflowにも注意する。浮動小数点では誤差のスケールを考え、epsilon付き比較をそのままsortの比較関数にしない。
下位単元
- 円環順序・chord交差 — 青色
問題一覧
- ABC248 E「K-colinear Line」 公式問題
技能・出典
主題: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。主タグ: 幾何の基本判定・配置・座標変換 / 補助タグ: 有界全列挙・有限case分解
- ABC437 F「Manhattan Christmas Tree 2」 公式問題組合せ: 区間monoid要約
技能・出典
主題: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: 幾何の基本判定・配置・座標変換 / 補助タグ: 区間monoid要約
- ABC442 E「Laser Takahashi」 公式問題
- ABC223 E「Placing Rectangles」 公式問題
技能・出典
主題: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。主タグ: 幾何の基本判定・配置・座標変換 / 補助タグ: 有界全列挙・有限case分解
- ABC366 E「Manhattan Multifocal Ellipse」 公式問題
技能・出典
主題: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。既習技能: 尺取り法・sliding windowで連続区間を走査する(一列の窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進められる。)。主タグ: 幾何の基本判定・配置・座標変換 / 補助タグ: 尺取り法・sliding window
- ABC426 E「Closest Moment」 公式問題
- ABC351 E「Jump Distance Sum」 公式問題組合せ: 局所寄与へ分解して集計順を交換する
技能・出典
主題: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。既習技能: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: 幾何の基本判定・配置・座標変換 / 補助タグ: 寄与の数え上げと順序交換
- ABC385 F「Visible Buildings」 公式問題
- ABC377 F「Avoid Queen Attack」 公式問題組合せ: 包除・Möbius反転で重複を補正する
技能・出典
主題: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。既習技能: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。)。主タグ: 幾何の基本判定・配置・座標変換 / 補助タグ: 集合上の包除原理
- ABC353 F「Tile Distance」 公式問題
技能・出典
主題: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。主タグ: 幾何の基本判定・配置・座標変換 / 補助タグ: 有界全列挙・有限case分解
- ABC296 G「Polygon and Points」 公式問題組合せ: event順にactive集合を更新する
技能・出典
主題: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。主タグ: 幾何の基本判定・配置・座標変換 / 補助タグ: event・値順のオフライン走査
- ABC258 F「Main Street」 公式問題
技能・出典
主題: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。主タグ: 幾何の基本判定・配置・座標変換 / 補助タグ: 有界全列挙・有限case分解
- ABC220 G「Isosceles Trapezium」 公式問題
技能・出典
主題: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。主タグ: 幾何の基本判定・配置・座標変換 / 補助タグ: 有界全列挙・有限case分解
- ABC234 Ex「Enumerate Pairs」 公式問題
技能・出典
主題: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。主タグ: 幾何の基本判定・配置・座標変換 / 補助タグ: 有界全列挙・有限case分解
- ABC301 G「Worst Picture」 公式問題
技能・出典
主題: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。主タグ: 幾何の基本判定・配置・座標変換 / 補助タグ: 有界全列挙・有限case分解
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC221 G「Jumping sequence」 公式問題
技能・出典
主題: bitsetで集合演算をword並列化する(集合をbit列へ符号化し、交差・和・shift・popcountをword並列に実行した計算量を評価できる。)。既習技能: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: bitsetによるword並列集合演算 / 補助タグ: 構成解・witness復元、幾何の基本判定・配置・座標変換
- ABC225 E「7」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 貪欲法と交換論 / 補助タグ: 幾何の基本判定・配置・座標変換
- ABC233 Ex「Manhattan Christmas Tree」 公式問題
技能・出典
主題: parallel binary search・多数境界の判定共有(各queryの未確定区間を保ち、同じroundのmidをbucketして一方向更新できる判定器を共有し、全queryの最小・最大成立境界を求められる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。) / 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: parallel binary search・多数境界の判定共有 / 補助タグ: event・値順のオフライン走査、Fenwick Tree・反転数・重み付き接頭辞統計、幾何の基本判定・配置・座標変換、累積和・差分配列
- ABC240 G「Teleporting Takahashi」 公式問題主題: 組合せ係数と対称性で数える
技能・出典
主題: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 組合せ係数・数え上げ / 補助タグ: 幾何の基本判定・配置・座標変換
- ABC243 Ex「Builder Takahashi (Enhanced version)」 公式問題主題: 最短路モデル
技能・出典
主題: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 最短路モデル / 補助タグ: 幾何の基本判定・配置・座標変換
- ABC250 F「One Fourth」 公式問題
技能・出典
主題: 尺取り法・sliding windowで連続区間を走査する(一列の窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進められる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 尺取り法・sliding window / 補助タグ: 幾何の基本判定・配置・座標変換
- ABC263 Ex「Intersection 2」 公式問題主題: 単調境界を証明して探索する
技能・出典
主題: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。既習技能: 円環順序・chord交差(円周をcutして端点を線形化し、交互配置またはlaminar括弧構造からchord交差を判定・数え上げできる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 単調境界探索 / 補助タグ: 円環順序・chord交差、event・値順のオフライン走査、Fenwick Tree・反転数・重み付き接頭辞統計、幾何の基本判定・配置・座標変換
- ABC266 Ex「Snuke Panic (2D)」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: event・値順のオフライン走査 / 補助タグ: 座標・値の順序保存圧縮、幾何の基本判定・配置・座標変換、区間monoid要約
- ABC274 F「Fishing」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: event・値順のオフライン走査 / 補助タグ: 幾何の基本判定・配置・座標変換
- ABC280 G「Do Use Hexagon Grid 2」 公式問題
技能・出典
主題: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。)。追加で学ぶ技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: 幾何の基本判定・配置・座標変換、集合上の包除原理 / 補助タグ: 寄与の数え上げと順序交換、event・値順のオフライン走査
- ABC283 F「Permutation Distance」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: event・値順のオフライン走査 / 補助タグ: 幾何の基本判定・配置・座標変換、区間monoid要約
- ABC314 Ex「Disk and Segments」 公式問題主題: 一次元凸・単峰最適化
技能・出典
主題: 一次元凸・単峰最適化(差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 一次元凸・単峰最適化 / 補助タグ: 幾何の基本判定・配置・座標変換
- ABC315 F「Shortcuts」 公式問題主題: 列・subsequence DP
技能・出典
主題: 列・subsequence DP(列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 列・subsequence DP / 補助タグ: 幾何の基本判定・配置・座標変換
- ABC323 F「Push and Carry」 公式問題主題: 同値な状態を正規化する
技能・出典
主題: 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 状態・配置の正規化 / 補助タグ: 有界全列挙・有限case分解、幾何の基本判定・配置・座標変換
- ABC343 E「7x7x7」 公式問題
技能・出典
主題: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。既習技能: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 有界全列挙・有限case分解 / 補助タグ: 幾何の基本判定・配置・座標変換、集合上の包除原理
- ABC405 F「Chord Crossing」 公式問題主題: laminar区間族の包含木構築
技能・出典
主題: laminar区間族の包含木構築(laminar区間の開閉端点をstackで処理し、直接包含関係と各点の最小包含区間を木として構築して、包含差分を木上pathへ変換できる。)。既習技能: ancestor query・LCA(binary lifting等を前計算し、level ancestor・LCA・木距離をqueryとして取得できる。) / 円環順序・chord交差(円周をcutして端点を線形化し、交互配置またはlaminar括弧構造からchord交差を判定・数え上げできる。)。主タグ: laminar区間族の包含木構築 / 補助タグ: 円環順序・chord交差、ancestor query・LCA
- ABC410 G「Longest Chord Chain」 公式問題主題: 値域集約による部分列DP
技能・出典
主題: 値域集約による部分列DP(末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 値域集約による部分列DP / 補助タグ: event・値順のオフライン走査、幾何の基本判定・配置・座標変換、区間monoid要約
- ABC418 E「Trapezium」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: 幾何の基本判定・配置・座標変換
- ABC422 E「Colinear」 公式問題
技能・出典
主題: 乱択の成功条件と誤り確率を設計する(乱数で選ぶ対象と成功条件を定め、誤り確率を上から評価して必要な反復回数または決定的な事後検証を設計できる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 乱択・Monte Carloアルゴリズム / 補助タグ: 幾何の基本判定・配置・座標変換
- ABC424 F「Adding Chords」 公式問題主題: 区間monoid要約
技能・出典
主題: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。既習技能: 円環順序・chord交差(円周をcutして端点を線形化し、交互配置またはlaminar括弧構造からchord交差を判定・数え上げできる。)。主タグ: 区間monoid要約 / 補助タグ: 円環順序・chord交差
- ABC457 G「Catch All Apples」 公式問題
技能・出典
主題: 半順序・Dilworth・最大反鎖(対象を半順序へ写し、Dilworth型のchain/antichain双対をLDS・matching・min-cutの適切な形で解ける。)。既習技能: LIS・末尾の支配関係(同じ長さなら小さい末尾が延長可能性を支配することを示し、長さ別最小末尾を二分探索で更新してLIS・非減少部分列を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 半順序・Dilworth・最大反鎖 / 補助タグ: 幾何の基本判定・配置・座標変換、LIS・末尾の支配関係
前提・学習成果・出典
習得対象の目安: 水色(1200–1599)。外積・端点順・座標変換を用い、退化ケースを含む位置関係を判定する。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 幾何・凸最適化。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-geometry-primitives
習得する技能
- 幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: 凸包・支持方向・境界候補、円環順序・chord交差、半平面制約・凸領域の共通部分。
座標と外積・距離式で向きや交差を代数判定し、凸幾何へ進む前提を作る。
このUnitでは扱わないもの
- 凸包の境界候補列挙・半平面交差。