HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > CEN112 Questions 2016 > problem:


15-FE-8. 50991 - Intersecting Circles

CEN112 Questions 2016

Start: Mar.30.2016 at 03:10:22 PM
Finish: Apr.01.2016 at 05:00:00 AM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 15-FE-1. 50992 - Top K Obese Classes
• 15-FE-2. 50993 - Products in store
• 15-FE-3. 50994 - The Most Crowded...
• 15-FE-4. 50995 - Group Average
• 15-FE-6. 50989 - Rectangles and Points
• 15-FE-7. 50990 - Two Neighbors
• 15-FE-8. 50991 - Intersecting C...
• 15-HW-2. 50932 - Shifting rows and...
• 15-HW-3. 50933 - Sum of the Bigges...
• 15-HW-4. 50934 - Selling Cars
• 15-HW-5. 50935 - Max Discount
• 15-MdtE-1. 50915 - Trip to Korca
• 15-MdtE-2. 50916 - Ascending Num...
• 15-MdtE-3. 50913 - Manhattan Distance
• 15-MdtE-4. 50917 - Descending Nu...

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.
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



Для отправки решений необходимо выполнить вход.

www.contester.ru