torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

AtCoder Beginner Contest 181, C : Collinearity

問題概要

 2 次元空間上の点が $N$ 個与えられる.同一直線上に乗る 3 点はあるか?

制約

  • $3 \leq N \leq 10^2$
  • 点の座標は相異なる

解法

 3 点の関係性を求めろ,ということなので 3 点の組合せを全て試すことを考えます.3 点 $i, j, k$ について,点 $i$ から点 $j$ へ引いた直線と点 $i$ から点 $k$ へ引いた直線の傾きが等しいとき,3 点 $i, j, k$ は同一直線上に乗ることが(脳内で図示することなどによって)分かります.傾きとは,$x$ 座標の差を $y$ 座標の差で割った値なので,これを有理数として見て一致するかどうかを判定することでほぼ答えが求まります.この方針の場合,$y$ 座標が一致しているときにゼロ除算をしないように気をつける必要があります.
 3 点の組合せを全て試すので,計算量は $\Theta( N^3 )$ となります.

コード

import Data.Ratio

main = do
	n <- readInt
	[ xs, ys ] <- transpose <$> replicateM n readInts
	putStrLn $ which "Yes" "No" $ not $ null $ do
		i <- [ 0 .. n - 1 ]
		j <- [ 0 .. n - 1 ]
		k <- [ 0 .. n - 1 ]
		guard $ i /= j && i /= k && j /= k
		let
			xi = xs !! i
			yi = ys !! i
			xj = xs !! j
			yj = ys !! j
			xk = xs !! k
			yk = ys !! k
		guard $ yi /= yj && yi /= yk && ( xj - xi ) % ( yj - yi ) == ( xk - xi ) % ( yk - yi ) || yi == yj && yi == yk
		return ()