E - Laser Pointer Experiment Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は物理の実験で、レーザーポインターを使った光の直進性に関する実験を行っています。

実験台の上の二次元平面上に N 個のセンサーが配置されています。i 番目のセンサー (1 \leq i \leq N) は座標 (X_i, Y_i) に置かれています。同じ座標に複数のセンサーが配置されることもありますが、それぞれ別のセンサーとして扱います。

高橋君はレーザーポインターを使って、平面上にレーザー光線を一度だけ照射します。レーザー光線は平面上の直線（両方向に無限に伸びるもの）として表されます。高橋君はこの直線を、センサーの位置に関係なく、平面上の任意の直線から自由に選ぶことができます。

各センサーは、そのセンサーの位置から直線までの距離（点と直線の最短距離）が D 以下であるとき反応します。ここで D はセンサーが反応する距離の閾値です。

このとき、反応するセンサーの個数を最大化してください。すなわち、平面上の直線 \ell を一つ選んだとき、点 (X_i, Y_i) から直線 \ell までの距離が D 以下であるようなセンサー i の個数の最大値を求めてください。

制約

  • 1 \leq N \leq 200
  • 0 \leq D \leq 1000
  • -1000 \leq X_i \leq 1000 (1 \leq i \leq N)
  • -1000 \leq Y_i \leq 1000 (1 \leq i \leq N)
  • 入力はすべて整数

入力

N D
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
  • 1 行目には、センサーの個数 N と、センサーが反応する距離の閾値 D が、スペース区切りで与えられる。
  • 2 行目から N+1 行目には、各センサーの座標が与えられる。i+1 行目 (1 \leq i \leq N) には、i 番目のセンサーの x 座標 X_i と y 座標 Y_i が、スペース区切りで与えられる。

出力

高橋君が一度のレーザー照射で同時に反応させることができるセンサーの最大個数を 1 行で出力せよ。

入力例 1

5 1
0 0
1 0
2 1
3 3
0 2

出力例 1

4

入力例 2

6 0
0 0
1 1
2 2
0 2
2 0
1 0

出力例 2

3

入力例 3

20 2
-5 -6
-4 -3
-3 -3
-2 -1
-1 -2
0 1
1 0
2 2
3 4
4 3
5 6
6 5
7 7
8 10
10 8
-8 5
-6 8
3 -7
9 -4
0 0

出力例 3

16

入力例 4

60 4
-30 -62
-28 -55
-26 -51
-24 -49
-22 -43
-20 -41
-18 -34
-16 -33
-14 -27
-12 -25
-10 -18
-8 -17
-6 -11
-4 -9
-2 -2
0 -1
2 5
4 7
6 14
8 15
10 21
12 23
14 30
16 31
18 37
20 39
22 46
24 47
26 53
28 55
30 62
-50 40
-45 -10
-40 70
-35 0
-32 100
-25 80
-15 60
-5 50
5 -50
15 -60
25 -70
35 -80
45 10
50 -40
60 60
-60 -60
0 80
80 0
-80 0
0 -80
100 100
-100 100
100 -100
-100 -100
12 23
12 23
-20 -41
31 60
-31 -60

出力例 4

36

入力例 5

1 1000
-1000 1000

出力例 5

1

Score : 466 pts

Problem Statement

Takahashi is conducting a physics experiment on the straightness of light using a laser pointer.

There are N sensors placed on a two-dimensional plane. The i-th sensor (1 \leq i \leq N) is located at the coordinates (X_i, Y_i). Multiple sensors may be placed at the same coordinates, but they are treated as distinct sensors.

Takahashi will project a laser beam onto the plane exactly once. The laser beam is represented as a straight line on the plane (extending infinitely in both directions). Takahashi can freely choose this line from any possible line on the plane, regardless of the positions of the sensors.

Each sensor reacts if the distance from the sensor's position to the line (the shortest distance between a point and a line) is at most D. Here, D is the threshold distance for the sensors to react.

Your task is to maximize the number of reacting sensors. That is, find the maximum number of sensors i such that the distance from the point (X_i, Y_i) to a chosen line \ell is at most D, over all possible lines \ell on the plane.

Constraints

  • 1 \leq N \leq 200
  • 0 \leq D \leq 1000
  • -1000 \leq X_i \leq 1000 (1 \leq i \leq N)
  • -1000 \leq Y_i \leq 1000 (1 \leq i \leq N)
  • All input values are integers.

Input

N D
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
  • The first line contains the number of sensors N and the threshold distance D for the sensors to react, separated by a space.
  • The next N lines, from the 2nd line to the (N+1)-th line, contain the coordinates of the sensors. The (i+1)-th line (1 \leq i \leq N) contains the x-coordinate X_i and the y-coordinate Y_i of the i-th sensor, separated by a space.

Output

Print the maximum number of sensors that Takahashi can simultaneously activate with a single laser projection in a single line.

Sample Input 1

5 1
0 0
1 0
2 1
3 3
0 2

Sample Output 1

4

Sample Input 2

6 0
0 0
1 1
2 2
0 2
2 0
1 0

Sample Output 2

3

Sample Input 3

20 2
-5 -6
-4 -3
-3 -3
-2 -1
-1 -2
0 1
1 0
2 2
3 4
4 3
5 6
6 5
7 7
8 10
10 8
-8 5
-6 8
3 -7
9 -4
0 0

Sample Output 3

16

Sample Input 4

60 4
-30 -62
-28 -55
-26 -51
-24 -49
-22 -43
-20 -41
-18 -34
-16 -33
-14 -27
-12 -25
-10 -18
-8 -17
-6 -11
-4 -9
-2 -2
0 -1
2 5
4 7
6 14
8 15
10 21
12 23
14 30
16 31
18 37
20 39
22 46
24 47
26 53
28 55
30 62
-50 40
-45 -10
-40 70
-35 0
-32 100
-25 80
-15 60
-5 50
5 -50
15 -60
25 -70
35 -80
45 10
50 -40
60 60
-60 -60
0 80
80 0
-80 0
0 -80
100 100
-100 100
100 -100
-100 -100
12 23
12 23
-20 -41
31 60
-31 -60

Sample Output 4

36

Sample Input 5

1 1000
-1000 1000

Sample Output 5

1