Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3370
Radio Waves

Time Limit: 10 Seconds      Memory Limit: 32768 KB      Special Judge

It is well known, that radio waves interfere, so if two closely located radio transmitters use the same frequency, the quality of the programs is poor.

The company NateRadio is planning to transmit its programs in Flatland. The Ministry of Health and Communications has issued the license to the company that allows it to use two different frequencies for the transmission.

The company has n slots for radio transmitters located at different points of the country. However, the transmitters themselves are not yet bought. The managers of the company want to know what power the transmitters should be. The power of the transmitter affects the range it transmits the radio program to.

All transmitters will have the same power. Transmitters will be installed into the slots and each will be tuned to one of the two allowed frequencies. The power of the transmitters must be selected in such a way that the programs from no two transmitters tuned to the same frequency are simultaneously received at any point. Each slot must be used.

Since the company wants the programs to be received by most people, it wants to install as powerful transmitters as possible --- the range of the transmission must be maximal.


The first line of the input file contains n --- the number of slots for the transmitters (3 ≤ n ≤ 1200). The following n lines contain two integer numbers each --- the coordinates of the corresponding slots. Coordinates do not exceed 104 by their absolute value. All slots are different.

There are multiple cases. Process to the end of file.


On the first line of the output file print the maximal possible range of the transmitters. On the second line print n integer numbers --- for each transmitter slot print 1 if the transmitter in this slot must use the first frequency, or 2 if it must use the second one.

You answer must be accurate up to 10-6. All inaccurances under this level will be resolved in your favor.

Sample Input

0 0
0 1
1 0
1 1

Sample Output

1 2 2 1

Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #11
Submit    Status