Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Question by Ibrahim Mesecan.
Intersecting Circles
You are famous after you solve math problems of
your brothers. Now, one of your neighbor needs
to count the number of intersecting circles
(adjacent, intersecting or overlapping). The
two circles are intersecting if the distance
between them is smaller than or equal to
the sum of the two radii.
Question:
You are given
the coordinates and radius of n circles. Find
the top k circles which intersect with
the most number of circles.
Input specification:
First, you will be given two integers: the number of
circles (n) and the number of top
intersecting circles to list (m).
The following n lines contain three integers:
center coordinate (x,y) and the radius
where 1 ≤ m ≤ n ≤ 5,000.
Output specification:
Show k integers (orders of top m circles).
If the two circles intersecting with the same
number of circles, first show the one which
appears before the other.
Sample Input
6 2
10 1 2
1 2 3
1 6 2
3 7 2
5 5 4
9 8 2
|
Sample Output
5 3
|
Explanation:
There are 6 circles given, and the top 2 circles will be listed.
Circle ID |
# of circles intersecting |
1 |
0 |
2 |
2 |
3 |
3 |
4 |
2 |
5 |
4 |
6 |
1 |
Для отправки решений необходимо выполнить вход.
|