Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

Your house is located at the origin of a 2-D plane. You have 'N' neighbours who live at 'N' different points on the plane. You want to visit exactly 'K' different neighbours who live closest to your house, you are given a 2 - D matrix 'POINTS'. So, find out the coordinates of the neighbours you are going to visit. The answer is guaranteed to be unique.

Note:

```
The distance between two points on a plane is the Euclidean Distance.
```

```
If N = 2, K = 1 and the points are {2,3}, {-1, 2}.
Then the distance of the first point from the origin is sqrt((2 - 0) ^ 2 + (3 - 0) ^ 2) = sqrt(13).
The distance of the second point from the origin is sqrt((-1 - 0) ^ 2 + (2 - 0) ^ 2) = sqrt(5).
```

```
Can you solve this in O(N log K) time complexity?
```

Detailed explanation

```
1 <= T <= 10
1 <= K <= N <= 10 ^ 4
-10 ^ 4 <= POINTS[i][0], POINTS[i][1] <= 10 ^ 4
Time limit: 1 sec.
```

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

```
-2 2 1 1
5 5
```

```
For the first test case, the distances of the points from the origin are sqrt(20), sqrt(8), sqrt(2), and sqrt(13) respectively. So, the 2 closest points are at a distance of sqrt(2) and sqrt(8) respectively. So, the points are (1, 1) and (-2, 2).
For the second test case, the only point (5, 5) is at a distance of sqrt(50). Hence, the point is (5, 5).
```

```
2
2 2
3 5 2 10
5 3
1 2 -2 2 3 0 0 -2 4 5
```

```
2 10 3 5
-2 2 0 -2 1 2
```

```
For the first test case, the distances of the points from the origin are sqrt(34) and sqrt(104) respectively. So, the 2 closest points are (2, 10) and (3, 5).
For the second test case, the distances of the points from the origin are sqrt(5), sqrt(8), sqrt(9), sqrt(4), and sqrt(41) respectively. So, the 3 closest points are at a distance of sqrt(4), sqrt(5), and sqrt(8) respectively. So, the points are (-2, 2), (0, -2) and (1, 2).
```