IMPC - 2013-2014 |
Start: Mar.16.2013 at 12:00:00 PM
Finish: Mar.16.2013 at 05:00:00 PM
The contest is finished!
• Contest scoreboard
|
Feedback | | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
bfs.
k-Nearest Neighbours (kNN)
{By Florenc Skuka}
Nearest neighbour (NN) is a very well-known
problem throughout data analysis and is often
utilized in a variety of different algorithms.
NN is an active area of research in computer
vision, genetic sequencing and string matching,
similarity search in unstructured databases,
data clustering and analysis, and a variety of
other artificial intelligence applications. Due
to its versatility, advances in the speed and
throughput of NN search often result in the
acceleration of other related data intensive
algorithms utilizing NN. Data algorithms such as
mean-shift clustering, point-cloud modelling for
image analysis, and content based image retrieval
are often accelerated by a fast NN search that limits
their model update and search space to only relevant,
or adjacent data.
Question:
Write a program that reads the coordinates of
points and find the total distance of k-Nearest
Neighbours for a given point.
Input specification
In the first line you are given 5 numbers (n, k, x, y, z)
- an integer number (n): number of points
where 0 ≤ n ≤ 100,000.
- an integer number (k)- the number of Nearest
Neighbours where 0 ≤ k ≤ 50,000
- three integers (x, y, z)- the coordinates
of the point for which we are searching the kNN.
Then, in the following n lines, you are given
coordinates (x, y, z) of n points
where x, y, z coordinates are between -800 and 800.
Output specification
Show the total distance of k-Nearest
Neighbours as floating point with 2
digits double precision
| Sample Input I |
Sample Output I |
9 4 3 2 4
756 449 435
-3 -7 6
448 -102 452
6 4 8
-508 -478 -250
16 -9 -11
-561 492 -731
1 3 7
-690 -455 -268
|
42.82
|
Для отправки решений необходимо выполнить вход.
|