Radio transmitters#712
If two transmitters operating on the same frequency are located too close to each other, the reception quality can degrade significantly. You are given the locations of transmitters. Each transmitter can use one of two available frequencies. All transmitters have the same power, denoted by , which represents the radius of reliable reception around the transmitter. Your task is to determine the greatest possible power such that there does not exist an area of positive size covered by two transmitters using the same frequency. You may choose the broadcasting frequency for each transmitter. Professor Knutman claims that there is a solution with a time complexity proportional to the square of , and this is efficient enough to fully solve the problem.
The first line contains the integer (3 \leq N \leq 7500), the number of transmitters. The following lines contain the coordinates of each transmitter. All coordinates are integers and their absolute value does not exceed . All transmitters have distinct coordinates.
Output the maximum possible power in the first line, with digits after the decimal point. On the second line, output numbers — the frequencies for the transmitters. The number at the -th position means the -th transmitter must use the first frequency, and means the second frequency. If there are several solutions, output any.
Example 1