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