102347: [AtCoder]ABC234 Ex - Enumerate Pairs
Description
Score : $600$ points
Problem Statement
Given are $N$ pairs of integers $(x_i,y_i)$, numbered $1$ to $N$, and an integer $K$.
List all pairs of integers $(p,q)$ that satisfy the conditions below, in the format specified in Output.
- $1 \le p < q \le N$
- $\sqrt{(x_p-x_q)^2+(y_p-y_q)^2} \le K$
Here, it is guaranteed that there are at most $4 \times 10^5$ such pairs of integers.
Constraints
- All values in input are integers.
- $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$
- There are at most $4 \times 10^5$ pairs of integers that should be listed.
Input
Input is given from Standard Input in the following format:
$N$ $K$ $x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_N$ $y_N$
Output
Print the answer in the following format.
$M$ $p_1$ $q_1$ $p_2$ $q_2$ $\vdots$ $p_M$ $q_M$
The first line should contain an integer $M$, representing the number of pairs of integers to be listed.
The subsequent $M$ lines should contain the pairs of integers to be listed $(p_i,q_i)$ in lexicographical order, each in its own line, separated by a space.
Here, a pair of integers $(a,b)$ comes before a pair of integers $(c,d)$ if and only if one of the following conditions is satisfied.
- $a<c$.
- $a=c$ and $b<d$.
Sample Input 1
6 5 2 0 2 2 3 4 0 0 5 5 8 3
Sample Output 1
9 1 2 1 3 1 4 2 3 2 4 2 5 3 4 3 5 5 6
There are $9$ pairs of integers that satisfy the conditions, which should be printed in the specified format.
$(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(5,6)$
Sample Input 2
2 1414213562 0 0 1000000000 1000000000
Sample Output 2
0
There may be zero pairs of integers that satisfy the conditions.
Sample Input 3
10 150 300 300 300 400 300 500 400 300 400 400 400 400 400 500 500 300 500 400 500 500
Sample Output 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
There may be pairs of integers $(i,j)$ ($i < j$) such that $x_i=x_j$ and $y_i=y_j$.
Input
题意翻译
给你平面上 $N$ 个点的坐标,问你有多少对点的欧几里得距离 $\leqslant K$,按字典序从小到大输出它们。保证答案点对数不超过 $4\times10^5$。Output
得分:600分
问题描述
给定编号为1到N的N对整数$(x_i,y_i)$,以及一个整数K。
- $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)$,每行一个整数对,由空格分隔。
这里,整数对$(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$。