题解

题面描述

给定一个超大智能汽车测试场，有 $n$ 个充电桩，每个充电桩的位置由二维平面坐标 $(x,y)$ 表示。给定智能汽车的当前位置 $(car_x, car_y)$，请设计一个高效的算法，找出距离（行驶距离）最近的 $k$ 个充电桩，并输出相关充电桩信息：编号、坐标、行驶距离。结果按行驶距离升序排序，若距离相等则按编号从小到大排序。行驶距离的计算方法为：

题目内容

一个超大智能汽车测试场有多个充电桩，每个充电桩的位置由其在二维平面上的坐标 $(x,y)$ 表示。给定一辆智能汽车的当前位置 $(car_x,car_y)$ ，请设计一个高效的算法，找出给定智能汽车行驶到充电桩行驶距离最近的 $k$ 个充电桩井输出相关充电桩信息(编号、坐标、行驶距离)，且按行驶距离升序排序(最近行驶距离的排在最前面)，如果存在行驶距离相等的充电桩则按照充电桩的编号从小到大输出。汽车到充电桩的行驶距离的计算方法为 $abs(car_{x-x})+abs(car_{y-y})$ 注意：$abs$ 表示绝对值。

输入描述

1，第一行是 $2$ 个整数 $k$ $n$，空格间隔，第 $1$ 个整数 $k$ 表示需要输出到的行驶距离最近的充电桩的数量 $(0<=k<=1000000)$ ，第 $2$ 个整数 $n$ 表示充电桩的总数量 $(0<n<=1000000)$ 。

2，第 $2$ 行是长度为 $2$ 的整数数组 $car_x$ $car_y$，中间是空格间隔，表示智能汽车的当前位置坐标。

3，第 $3$ 行到第 $n+2$ 行是编号为 $1$ 到 $n$ 的充电桩的位置坐标

注意：坐标数值大小区间为：$[-2^{32},2^{31-1}]$

输出描述

一个二维数组，每一行是一个长度为 $4$ 的数组：编号 $x$ $y$ $distance$ ，编号表示充电桩的编号(介于 $1$ 到 $n$ 之间)、$x$ $y$ 表示充电的坐标, $distance$ 表示智能汽车到充电桩的行驶距离，从第 $1$ 行开始往下是按距离从小到大排序的。如果存在行驶距离相等的充电桩则按照充电桩的编号从小到大输出。如果 $k$ 为 $0$ 或者 $k$ 大于 $n$ ，输出字符串 $null$ 。

样例1

输入

3 5
0 0
1 4
5 6
2 3
7 8
3 -1

输出

5 3 -1 4
1 1 4 5
3 2 3 5

说明

到汽车行驶距离最近的三个充电桩的编号分别为 $5、1、3$ ，充电桩的坐标分别是 $3$ $-1$、$1$ $4$、$2$ $3$ ，到智能汽车坐标 $[0,0]$ 的行驶距离分别为 $4、5、5$。距离都为 $5$ 的充电桩 $1$ 的编号小于编号 $3$ 的充电桩，输出结果中编号小的在前。

样例2

输入

0 5
0 0
1 5
5 6
2 3
7 8
3 -1

输出

null

说明

$k$ 的值是 $0$ ，输出 $null$ 字符串