Radio transmitters
If two transmitters operating on the same frequency are placed too close to each other, the reception quality can degrade significantly. You are provided with the locations of N transmitters, each of which can operate on one of two available frequencies. All transmitters have the same power level, denoted as W, which represents the radius within which reception is reliable. Your task is to determine the maximum power W such that no area of positive size exists where two transmitters using the same frequency have overlapping reception areas. You have the flexibility to assign the broadcasting frequency for each transmitter. Professor Knutman asserts that there is a solution to this problem that can be found in time proportional to the square of N, which is efficient enough to fully resolve the problem.
Input
The first line of the input file contains an integer N (3 ≤ N ≤ 7500), representing the number of transmitters. The following N lines provide the coordinates of each transmitter. All coordinates are integers and do not exceed 10000 in absolute value. Each transmitter is located at a unique coordinate.
Output
On the first line, output the maximum power W for the transmitters, formatted to 7 decimal places. On the second line, output N numbers, indicating the frequency assignment for each transmitter. A 1 in the i-th position signifies that the i-th transmitter should use the first frequency, while a 2 indicates the second frequency. If multiple solutions exist, any valid solution may be provided.