102347: [AtCoder]ABC234 Ex - Enumerate Pairs

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$.

问题描述

给定编号为1到N的N对整数$(x_i,y_i)$，以及一个整数K。

• $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$

第一行应包含一个整数$M$，表示需要列出的整数对的数量。
随后的$M$行应按照字典序列出需要列出的整数对$(p_i,q_i)$，每行一个整数对，由空格分隔。
这里，整数对$(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

可能没有满足条件的整数对。

样例输入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

可能存在整数对$(i,j)$ ($i < j$)，使得$x_i=x_j$且$y_i=y_j$。