Кольорові кола#373

Кольорові кола (Розбір)

Автор задачі:

Олександр Тимкович

Задачу підготували:

Павло Ціцей, Олександр Тимкович

Розбір написав:

Павло Ціцей

Припустимо, що кожне є унікальним. Для цього ми можемо взяти всі кола з центром x_i і припустити, що є лише одне з найбільшим радіусом. Для всіх інших ми можемо їх обертати, якщо обертаємо це, та навпаки.

Щоб вирішити це завдання, ми відсортуємо всі кола в порядку зростання їх центрів. Якщо в цьому колі є інший центр, то відповідь буде , оскільки немає способу обертати чи не обертати, щоб задовольнити умову в цьому випадку. В іншому випадку, подивімося на попереднє коло. Якщо воно перетинається з нашим, тоді нам потрібно обернути його, якщо останнє не оберталося, і навпаки.