← 返回题目列表

AtCoder · abc234_h

Ex. 枚举对

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给出的是 N 整数对 (x_i,y_i),编号 1 to N,和一个整数 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

第一行应包含一个整数 M,表示要列出的整数对的数量。
后续 M 行应包含要列出的整数对 (p_i,q_i) in 字典顺序,每个都在自己的行中,用空格分隔。
这里,一对整数 (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.