[ABC234Ex] Enumerate Pairs

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

[problemUrl]: https://atcoder.jp/contests/abc234/tasks/abc234_h $ 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 $ である。

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 $) が存在する場合もあります。