「部外者をはじけ」を解くために:part5 Scala編（paizaランク C 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
part4 では直線と点の距離を計算しました。
これを利用して部外者の数を数えてみましょう。
N 人の人物の二次元座標 (x_i, y_i) が与えられます。
(x_1, y_1) と (x_2, y_2) を結ぶ直線を引いたとき、部外者の数を求めてください。
ただし、部外者とは直線から 2 m以上離れた人を指します。
ここで、任意の二点 (x_1, y_1), (x_2, y_2) を結ぶ直線の方程式 ax - by + c = 0 は次のように計算できます。
(y_2-y_1) * x - (x_2-x_1) * y + {(x_2-x_1) * y_1 - (y_2-y_1) * x_1} = 0
また、ある点 (x_i,y_i) と直線 ax + by + c = 0 との距離 d_i は次のように求まります。
d_i = |a * x_i + b * y_i + c| / (a^2 + b^2)^(1/2)
- 入力される値
-
N
x_1 y_1
.
.
.
x_N y_N
・1 行目には、検出した人の数 N が入力されます。
・i+1 (1 ≦ i ≦ N) 行目には、i 番目の人物の二次元座標 (x_i, y_i) が空白区切りで与えられます。
・なお、座標の単位は [m] で、座標はそれぞれ小数点以下 2 桁までの小数で与えられます。
・入力は合計 N + 1 行からなり、末尾に改行を 1 つ含みます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
(x_1, y_1) と (x_2, y_2) を結ぶ直線を引いたときの部外者の数を一行に出力してください。
出力の末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースで以下の条件を満たします。
・ 2 ≦ N ≦ 100
・ 0 ≦ (部外者の数) < (N/2)
・ 0 ≦ x_i < 640
・ 0 ≦ y_i < 480
・ (x_i,y_i) ≠ (x_j,y_j) (i ≠ j)
- 入力例1
-
20
331.26 330.83
264.31 3.44
118.56 118.09
162.59 162.15
329.92 330.36
271.86 272.05
371.44 371.42
340.22 340.48
286.67 286.36
466.66 466.17
407.49 407.67
381.02 381.45
271.05 270.96
39.97 39.84
464.65 464.65
352.98 352.62
260.1 260.41
31.92 31.92
476.45 139.5
184.83 185.22
- 出力例1
-
17
- 入力例2
-
2
210.43 423.86
104.71 212.42
- 出力例2
-
0
