問題概要
2 次元空間上に $N$ 個の点があり,$i$ 番目の点の座標は $( X_i, Y _i )$ である.
これらの内,原点からの距離が $D$ 以下であるようなものはいくつあるか?
制約
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq D \leq 2 \times 10^5$
- $| X_i |, | Y_i | \leq 2 \times 10^5$
解法
一つ一つの点について条件を満たすか判定し,満たすものを数えることで解くことができます.
ただし,注意点が 2 つあって,
- 平方根をとると実数になって誤差がこわいので両辺を 2 乗する
- そうすると今度は 32 bit 整数がオーバーフローするのでもうちょっと大きな整数型を使う
という風にする必要があります.
コード
main = do [ n, d ] <- readIntegers ps <- map mp <$> replicateM ( fromIntegral n ) readIntegers print $ length $ filter ( f d ) ps f d ( x, y ) = x ^ 2 + y ^ 2 <= d ^ 2