题目内容

在一座超大智能汽车测试场中，分布着多个充电桩，充电桩的编号为从 1 到 n 的整数，每个充电桩的位置由二维平面坐标 $(x, y)$ 表示。测试场内有一辆智能汽车，其当前位置坐标为 $(car_x, car_y)$。

对于任意一个坐标为 $(x, y)$ 的充电桩，定义智能汽车到该充电桩的行驶距离为：

其中 $|a|$ 表示 $a$ 的绝对值。

现在需要从所有充电桩中找出行驶距离最近的 k 个充电桩，并输出这些充电桩的编号、坐标以及对应的行驶距离。

约束条件

• k 和 n 均为整数，且 $0 \le k \le 10^6$，$1 \le n \le 10^6$。
• 所有坐标值均位于区间 $[-2^{32}, 2^{31-1}]$ 内。

输入描述

第一行包含两个整数 k 和 n，用空格分隔。

第二行包含两个整数 car_x 和 car_y，用空格分隔，表示智能汽车的当前位置坐标。

接下来 n 行，每行包含两个整数 x 和 y，用空格分隔，依次表示编号为 1 到 n 的充电桩的坐标。

输出描述

如果 k 等于 0，或者 k 大于 n，则输出一行字符串 null。

否则输出 k 行，每行包含四个整数：充电桩编号、横坐标 x、纵坐标 y、行驶距离 distance，用空格分隔。所有输出行按行驶距离升序排列；若行驶距离相同，则按充电桩编号升序排列。

样例1

输入

3 4
1 -1
1 0
2 -1
-1 1
1 2

输出

1 1 0 1
2 2 -1 1
4 1 2 3

说明

汽车坐标为 $(1,-1)$。

编号 1 的充电桩坐标为 $(1,0)$，距离 $d=|1-1|+|-1-0|=1$。 编号 2 的充电桩坐标为 $(2,-1)$，距离 $d=|1-2|+|-1-(-1)|=1$。 编号 3 的充电桩坐标为 $(-1,1)$，距离 $d=|1-(-1)|+|-1-1|=4$。 编号 4 的充电桩坐标为 $(1,2)$，距离 $d=|1-1|+|-1-2|=3$。

需要输出距离最近的 3 个充电桩，因此距离为 4 的编号 3 被排除。编号 1 和编号 2 距离相同，按编号升序排列，所以输出顺序为编号 1、编号 2、编号 4。

样例2

输入

0 3
0 0
1 1
2 2
3 3

输出

null

说明

因为 k 等于 0，根据规则不输出任何有效充电桩信息，所以只输出字符串 null。输入的 3 个充电桩坐标不会作为有效结果输出。

样例3

输入

4 2
0 0
5 5
7 8

输出

null

说明

这里 k 等于 4，而充电桩总数 n 等于 2，满足 k > n，因此不输出任何有效充电桩信息，只输出字符串 null。

样例4

输入

1 1
10 10
-5 2

输出

1 -5 2 23

说明

只有 1 个充电桩，且 k 等于 1，因此需要输出该充电桩。

汽车坐标为 $(10,10)$，充电桩坐标为 $(-5,2)$。 行驶距离 $d=|10-(-5)|+|10-2|=15+8=23$。

因此输出编号 1、坐标 $(-5,2)$、距离 23。

开通会员即可查看完整视频题解：1.题目讲解 2.思路分析 3.逐行代码手写