Problem description：
Given
N
N
N points on the plane. Find the
K
t
h
Kth
Kth closest point to the origin
(
0
,
0
)
(0,0)
(0,0). (Here, the distance between two points on a plane is the Euclidean distance.)
Input：
Line 1:
N
N
N
K
K
K
Others: point coordinate
Output：
Line 1:
K
t
h
Kth
Kth closest point to the origin
(
0
,
0
)
(0,0)
(0,0)
Sample Input 1：
2 1
1 3
-2 2
Sample Output 1：
-2 2
Solution1：
#include <iostream>
#include <cstdio>
#include <cmath>
#include<algorithm>
using namespace std
;
struct point
{
long long int x
;
long long int y
;
unsigned long long int distance
;
};
bool cmp(point a
, point b
){
return a
.distance
< b
.distance
;
}
int main()
{
int n
, k
;
scanf("%d%d",&n
, &k
);
const int N
=n
, K
=k
;
point points
[N
];
int i
;
for(i
=0; i
<N
; i
++){
scanf("%lld%lld",&points
[i
].x
, &points
[i
].y
);
points
[i
].distance
= ((points
[i
].x
)*(points
[i
].x
)) + ((points
[i
].y
)*(points
[i
].y
));
}
sort(points
, points
+N
, cmp
);
cout
<< points
[K
-1].x
<< ' ' << points
[K
-1].y
<< endl
;
return 0;
}
注意1:
算法首先求出所有点到
(
0
,
0
)
(0,0)
(0,0)的距离，然后sort排序直接求出距离
(
0
,
0
)
(0,0)
(0,0)第K近的点。算法复杂度和空间复杂度较高。可通过创建结构体存储点的坐标。sort函数有三个参数，第三个参数可以制定排序规则。
