Радіопередавачі#712
Якщо два передавачі працюють на одній частоті та розташовані надто близько один до одного, якість прийому може значно погіршитися. Вам задано розташування передавачів. Кожен передавач може використовувати одну з двох доступних частот. Потужності всіх передавачів однакові й позначаються як , що є радіусом надійного прийому навколо передавача. Ваше завдання — визначити найбільшу можливу потужність так, щоб не існувало області додатної площі, яку покривають два передавачі, що працюють на одній частоті. Ви можете самостійно вибрати частоту для кожного передавача. Професор Кнутмен стверджує, що існує розв'язок із часовою складністю, пропорційною квадрату , і цього достатньо для повного розв'язання задачі.
У першому рядку міститься ціле число (3 \leq N \leq 7500) — кількість передавачів. У наступних рядках зазначені координати кожного передавача. Усі координати — цілі числа, що не перевищують за модулем. Кожен передавач розташовано в унікальних координатах.
У першому рядку виведіть максимальну можливу потужність з знаками після десяткової крапки. У другому рядку виведіть чисел — частоти для передавачів. Число у -ій позиції означає, що -ий передавач використовує першу частоту, а — другу частоту. Якщо існує декілька розв'язків, виведіть будь-який.
Приклад 1