分数: 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.