Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 248 E問題 K-colinear Line

AtCoder ABC ABC248 E問題 500 pts

問題

提出解答

問題の概要

座標平面上に異なる $N$ 点 $P_1=(X_1, Y_1), \dots, P_N=(X_N, Y_N)$ がある.

このとき, $K$ 点以上を通る直線の数を求め, 有限ならばその数を無限ならばその旨を報告せよ.

制約

$1 \leq N \leq 300$
$|X_i|, |Y_i| \leq 10^9$
$P_i \neq P_j$

解法 1 ( $K=1$ のとき)

$K=1$ のとき, $-\pi/2 \lt \theta \lt \pi/2$ に対して, 直線 $\ell_\theta: y=(\tan \theta) (x-X_1)+Y_1$ は点 $P_1$ を通る直線であり, 写像 $(-\pi/2, \pi/2) \to \ell_\theta$ は単射である. よって, $P_1$ を通る直線が無限個あることから, 求めるべき答えは無限である.

解法 2 ( $K \geq 2$ のとき)

$K \geq 2$ とする. このとき, 以下のような事実がある.

Euclid 幾何における公準 I (+ $\alpha$ )

相異なる2点を通る直線は唯一存在する.

この事実から, 条件を満たすような直線は高々 $\dbinom{N}{2}=\dfrac{N(N-1)}{2}$ 本であることがわかる. そして, そのような直線は相異なる2点 $P_i, P_j$ を通る直線達から導くことができる.

よって, 次のようにして計算できる.

$S \gets \emptyset$
を満たすに対して, 以下を行う.
- $P_i$ と $P_j$ を通る直線 $m_{i,j}$ を求める.
- $m_{i,j}$ 上にある点 $P_1, \dots, P_N$ の数 $\lambda_{i,j}$ を求め, $\lambda_{i,j} \geq K$ ならば, $S$ に $m_{i,j}$ を加える.
$S$ の濃度を加える.

直線を管理する際, $y=ax+b$ という形で記録するよりも, $ax+by+c=0$ の方が管理しやすい. また, この方式では, 一見見た目が異なっていても同じ式の場合がある *1.

これにより, 計算量 $O(N^3)$ で求めることができる.

*1:例 : $2x+3y+4=0$ と $4x+6y+8=0$