Ex - Enumerate Pairs 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

1 から N までの番号のついた N 個の整数の組 (x_i,y_i) と、整数 K が与えられます。
以下の条件を満たす整数の組 (p,q) を「出力」で指定する形式に従ってすべて列挙してください。

  • 1 \le p < q \le N
  • \sqrt{(x_p-x_q)^2+(y_p-y_q)^2} \le K

ただし、そのような整数の組が 4 \times 10^5 組以下であることは保証されます。

制約

  • 入力はすべて整数
  • 1 \le N \le 2 \times 10^5
  • 1 \le K \le 1.5 \times 10^9
  • 0 \le x_i,y_i \le 10^9
  • 列挙すべき整数の組は 4 \times 10^5 組以下である

入力

入力は以下の形式で標準入力から与えられる。

N K
x_1 y_1
x_2 y_2
\vdots
x_N y_N

出力

以下の形式で出力せよ。

M
p_1 q_1
p_2 q_2
\vdots
p_M q_M

まず、 1 行目に整数 M を出力せよ。 M は出力する整数の組の個数を表す。
続く M 行に、列挙するべき整数の組 (p_i,q_i) を 1 行に 1 つずつ空白区切りで、 辞書順で 出力せよ。
ただし、整数の組 (a,b),(c,d) が以下の条件のどちらかを満たすとき、またその時に限り、 整数の組 (a,b) が整数の組 (c,d) より辞書順で前であるとする。

  • a<c である。
  • a=c であり、かつ b<d である。

入力例 1

6 5
2 0
2 2
3 4
0 0
5 5
8 3

出力例 1

9
1 2
1 3
1 4
2 3
2 4
2 5
3 4
3 5
5 6

条件を満たす整数の組は以下の 9 個なので、これを出力形式に従って出力して下さい。
(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(5,6)

入力例 2

2 1414213562
0 0
1000000000 1000000000

出力例 2

0

条件を満たす整数の組が 0 組である場合もあります。

入力例 3

10 150
300 300
300 400
300 500
400 300
400 400
400 400
400 500
500 300
500 400
500 500

出力例 3

29
1 2
1 4
1 5
1 6
2 3
2 4
2 5
2 6
2 7
3 5
3 6
3 7
4 5
4 6
4 8
4 9
5 6
5 7
5 8
5 9
5 10
6 7
6 8
6 9
6 10
7 9
7 10
8 9
9 10

x_i=x_j かつ y_i=y_j であるような整数の組 (i,j) (i < j) が存在する場合もあります。

Score : 600 points

Problem Statement

Given are N pairs of integers (x_i,y_i), numbered 1 to N, and an integer K.
List all pairs of integers (p,q) that satisfy the conditions below, in the format specified in Output.

  • 1 \le p < q \le N
  • \sqrt{(x_p-x_q)^2+(y_p-y_q)^2} \le K

Here, it is guaranteed that there are at most 4 \times 10^5 such pairs of integers.

Constraints

  • All values in input are integers.
  • 1 \le N \le 2 \times 10^5
  • 1 \le K \le 1.5 \times 10^9
  • 0 \le x_i,y_i \le 10^9
  • There are at most 4 \times 10^5 pairs of integers that should be listed.

Input

Input is given from Standard Input in the following format:

N K
x_1 y_1
x_2 y_2
\vdots
x_N y_N

Output

Print the answer in the following format.

M
p_1 q_1
p_2 q_2
\vdots
p_M q_M

The first line should contain an integer M, representing the number of pairs of integers to be listed.
The subsequent M lines should contain the pairs of integers to be listed (p_i,q_i) in lexicographical order, each in its own line, separated by a space.
Here, a pair of integers (a,b) comes before a pair of integers (c,d) if and only if one of the following conditions is satisfied.

  • a<c.
  • a=c and b<d.

Sample Input 1

6 5
2 0
2 2
3 4
0 0
5 5
8 3

Sample Output 1

9
1 2
1 3
1 4
2 3
2 4
2 5
3 4
3 5
5 6

There are 9 pairs of integers that satisfy the conditions, which should be printed in the specified format.
(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(5,6)

Sample Input 2

2 1414213562
0 0
1000000000 1000000000

Sample Output 2

0

There may be zero pairs of integers that satisfy the conditions.

Sample Input 3

10 150
300 300
300 400
300 500
400 300
400 400
400 400
400 500
500 300
500 400
500 500

Sample Output 3

29
1 2
1 4
1 5
1 6
2 3
2 4
2 5
2 6
2 7
3 5
3 6
3 7
4 5
4 6
4 8
4 9
5 6
5 7
5 8
5 9
5 10
6 7
6 8
6 9
6 10
7 9
7 10
8 9
9 10

There may be pairs of integers (i,j) (i < j) such that x_i=x_j and y_i=y_j.