题目描述

$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$ 組以下であることは保証されます。

输入格式

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

$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$ である。

题目大意

给你平面上 $N$ 个点的坐标，问你有多少对点的欧几里得距离 $\leqslant K$，按字典序从小到大输出它们。保证答案点对数不超过 $4\times10^5$。

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

2 1414213562
0 0
1000000000 1000000000

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

提示

制約

• 入力はすべて整数
• $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$ 組以下である

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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