ABC 248 E — K-colinear Line

考察

K=1 なら、与えられた任意の 1 点を通る直線だけでも傾きを連続的に変えられるため無限本存在する。

K≥2 なら条件を満たす直線は必ず与えられた相異なる 2 点で一意に定まり、候補は点対から得られる有限個に限られる。

採用する候補: 全点対が定める直線について全 N 点の共線性を外積で調べ、K 点以上なら正規化した直線表現を set に入れる。

N≤300 なので点対×全点を調べられ、正規化 key により同一直線を一度だけ数えられる。

棄却する候補: 各点対が K 点以上を通るたびに、そのまま答えを 1 増やす。

m 点が同一直線上にあると同じ直線を mC2 回数えてしまい、重複除去がない。

点 A,B,P の共線条件は (B_x-A_x)(P_y-A_y)=(B_y-A_y)(P_x-A_x) で、傾きの除算を使わず垂直線も同じ式で扱える。

直線 Ax+By+C=0 の係数を gcd で割り、最初の非零係数が正になるよう符号をそろえると、同一直線が同一の整数 tuple になる。

K=1 なら Infinity を出力する。それ以外は i<j の各点対から直線を作り、全点を外積で数えて K 以上なら canonical (A,B,C) を set へ挿入し、set size を答える。

典型の発動条件

2 点で決まる候補の全列挙

発動条件: 求める幾何対象が任意の 2 入力点で一意に決まり、N が数百程度のとき。

O(N^2) 個の候補直線ごとに全点の共線性を検査する。

整数係数による幾何正規化

発動条件: 同じ直線や方向を浮動小数なしで重複排除したいとき。

直線係数を gcd と符号で canonicalize し、tuple を set key にする。

問題固有の要素

K=1 の無限性と K≥2 の『必ず点対で決まる』を分けることで、連続な直線集合が有限候補列挙へ変わる。

別の問題へ持ち帰る視点: 幾何数え上げでは、必要な入力点数で対象が一意に決まる閾値を先に確認し、退化時だけ別処理する。

正当性

K=1なら各点を通る無限の直線が存在する。K≥2の有効直線は必ず入力点の対から生成されるので、全点対を調べれば漏れない。外積0で所属点数を正確に求め、gcdと符号で正規化した(A,B,C)の集合へ入れると、どの点対で生成しても同じ直線は一度だけ数えられる。座標積には浮動小数を使わない。

実装上の注意

  • 座標差と積は大きくなるため、外積および C 係数の計算には十分な幅の整数型を使う。
  • 垂直線・水平線も含めて gcd(|A|,|B|,|C|) と符号規約を一貫させ、同じ線の点対順による符号反転を除く。

復習の核

  • 3 点が同一直線上にある例で 3 点対が 1 key に潰れることと、K=1 だけが Infinity になる理由を別々に確認する。

計算量と制約

時間

O(N³+N² log N log V)。Vは係数の最大絶対値。

空間

O(N²)(直線keyの集合)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq K \leq N \leq 300; \lvert X_i \rvert, \lvert Y_i \rvert \leq 10^9; X_i\neq X_j or Y_i\neq Y_j, if i\neq j.; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

K-colinear Line の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 幾何の基本判定と座標変換

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 幾何の基本判定・配置・座標変換

    補助タグ: 有界全列挙・有限case分解

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

    学習の位置

    体系上の位置: 幾何の基本判定と座標変換

    • 幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。

    先に読む単元:

    この解説で扱わないこと:

    • 凸包の境界候補列挙・半平面交差。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題