枚举数对

题目描述

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

按输出格式中指定的方式列出所有满足以下条件的整数对 $(p,q)$。

$1 \le p \lt q \le N$

$\sqrt{(x_p-x_q)^2+(y_p-y_q)^2} \le K$

这里,保证满足条件的整数对至多有 $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 \lt c$

$a = c$ 且 $b \lt d$

样例

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

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 1414213562
0 0
1000000000 1000000000

0

满足条件的整数对可能为 $0$ 对。

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

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 \lt j$)。

数据范围

• 输入中的所有值均为整数。
• $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$ 对。