Description
There are N points in a D-dimensional Euclidean space.
Given a test point x, find its kth nearest neighbor among the N points.
Input
The first line contains three integers N, D, k representing the number of points, the dimension, and the parameter k for k-nearest neighbor. The next N lines contain the coordinates of the N points. The last line contains the coordinate of the test point x.
For example, consider the following five points in 2-dimensional space.
(0.0, 0.0), (5.0, 0.0), (5.0, 5.0), (0.0, 5.0), (2.5, 2.5)
The test point is (-1.0, 0.5). Suppose that we want to find its 3rd nearest neighbor (k=3). The answer is the point (0.0, 5.0). Use printf “%.1f” format to show the decimal values.
It is guaranteed that
- 0 < N, D ≤ 1000
- k ≤ 30
- All coordinate values can be represented by float
Output
The kth nearest neighbor of x among the N points.
(We guarantee that the kth nearest neighbor of x is unique.)
Use printf “%.1f” format to show the decimal value.
There is a newline character ‘\n’ at the end of line.