ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > CEN112 Questions 2016 > задача:


15-FE-8. 50991 - Intersecting Circles

CEN112 Questions 2016

Старт: 30.мар.2016 в 15:10:22
Финиш: 01.апр.2016 в 05:00:00
Турнир завершён!
• Турнирная таблица

Гость
• Вопросы к жюри (1)

Задачи турнира

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

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 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



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

www.contester.ru