Автор задачі: | Олександр Тимкович |
Задачу підготували: | Павло Ціцей, Олександр Тимкович |
Розбір написав: | Павло Ціцей |
Припустимо, що кожне є унікальним. Для цього ми можемо взяти всі кола з центром x_i і припустити, що є лише одне з найбільшим радіусом. Для всіх інших ми можемо їх обертати, якщо обертаємо це, та навпаки.
Щоб вирішити це завдання, ми відсортуємо всі кола в порядку зростання їх центрів. Якщо в цьому колі є інший центр, то відповідь буде , оскільки немає способу обертати чи не обертати, щоб задовольнити умову в цьому випадку. В іншому випадку, подивімося на попереднє коло. Якщо воно перетинається з нашим, тоді нам потрібно обернути його, якщо останнє не оберталося, і навпаки.