Радіопередавачі
Відомо, що якщо поряд розміщені два передавачі, які працюють на одній частоті, то якість прицому різко погіршується. Вам задано місцезнаходження N передавачів. Відомо, що кожен з них може використовувати одну з двох доступних частот. потужності всіх передавачів однакові між собою і рівні W. В даному випадку під потужністю розуміється радіус дії впевненого прийому навколо передавача. Яку найбільшу потужність W можуть мати ці передавачі, щоб не існувало області додатної площі впевненого прийому двох передавачів, які транслюють на однаковій частоті? Вибір частоти мовлення кожного передавача залишається за вами. Професср Кнутмен стверджує, що існує розв'язок цієї задачі за час, пропорційний квадрату числа N, і цей розв'язок достатньо ефективний для повного розв'язання цієї задачі.
Вхідні дані
У першому рядку вхідного файлу міститься ціле число N (3 ≤ N ≤ 7500) - кількість передавачів. Далі в N рядках записані координати кожного передавача. Всі координати - цілі числа, які не перевищують 10000 по абсолютній величині. Всі передавачі мають різні координати.
Вихідні дані
У перший рядок виведіть максимальну потужність передавачів W. Потужність виводьте з 7 знаками після коми. У другому рядку виведіть N чисел - номер частот передавачів. Число 1 в i-тій позиції означає, що i-ий передавач повинен вести мовлення на першій частоті. Число 2 означає, що на другій. Якщо розв'язків декілька, виведіть довільний.