题目详情题解（0）讨论（0）提交记录（0）

AT_abc234_h.[ABC234Ex] Enumerate Pairs

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

  • 1≤p<q≤N1 \leq p < q \leq N
  • (xp−xq)2+(yp−yq)2≤K\sqrt{(x_p - x_q)^2 + (y_p - y_q)^2} \leq K

保证满足条件的整数对不会超过 4×1054 \times 10^5 组。

输入格式

输入通过标准输入给出，格式如下：

NN KK
x1x_1 y1y_1
x2x_2 y2y_2
⋮\vdots
xNx_N yNy_N

输出格式

请按如下格式输出：

MM
p1p_1 q1q_1
p2p_2 q2q_2
⋮\vdots
pMp_M qMq_M

首先，在第 11 行输出整数 MM，表示需要枚举的整数对的个数。
接下来 MM 行，每行输出一个需要枚举的整数对 (pi,qi)(p_i, q_i)，用空格分隔，按字典序排列。
对于整数对 (a,b)(a, b) 和 (c,d)(c, d)，当且仅当满足以下任一条件时，(a,b)(a, b) 在字典序上优先于 (c,d)(c, d)：

  • a<ca < c；
  • a=ca = c 且 b<db < 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

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

说明/提示

限制条件

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

样例解释 1

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

样例解释 2

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

样例解释 3

也可能存在 xi=xjx_i = x_j 且 yi=yjy_i = y_j 的整数对 (i,j)(i, j)（i<ji < j）。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页