AT_abc234_h [ABC234Ex] Enumerate Pairs

题目描述

给定 $N$ 个编号为 $1$ 到 $N$ 的整数对 $(x_i, y_i)$，以及一个整数 $K$。
请按照指定的输出格式，枚举所有满足以下条件的整数对 $(p, q)$：

• $1 \leq p < q \leq N$
• $\sqrt{(x_p - x_q)^2 + (y_p - y_q)^2} \leq 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$ 行，每行输出一个需要枚举的整数对 $(p_i, q_i)$，用空格分隔，按字典序排列。
对于整数对 $(a, b)$ 和 $(c, d)$，当且仅当满足以下任一条件时，$(a, b)$ 在字典序上优先于 $(c, d)$：

• $a < c$；
• $a = c$ 且 $b < d$。

输入输出样例 #1

输入 #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

输入输出样例 #2

输入 #2

2 1414213562
0 0
1000000000 1000000000

输出 #2

0

输入输出样例 #3

输入 #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

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq 1.5 \times 10^9$
• $0 \leq x_i, y_i \leq 10^9$
• 需要枚举的整数对不会超过 $4 \times 10^5$ 组。

样例解释 1

满足条件的整数对共有 $9$ 组，请按输出格式输出：$(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(5,6)$。

样例解释 2

也有可能不存在满足条件的整数对，此时输出 $0$。

样例解释 3

也可能存在 $x_i = x_j$ 且 $y_i = y_j$ 的整数对 $(i, j)$（$i < j$）。

由 ChatGPT 4.1 翻译