Cell phone towers

Given up to 40 house coordinates, find the smallest common radius so that two circles of that radius can cover every house.

Medium6GeometryBinary searchBrute forceNo attempts yetTime limit2sMemory limit512 MB

Problem

A phone company wants to start home phone service in your city. The phones stay in the houses, but the company uses cellular technology with transmission towers so it does not have to pay for a cable network across the whole city.

The power of the transmitter and receiver installed on a tower fixes the coverage radius of that tower. The city is perfectly flat, so the area one tower covers is a circle. The price of the equipment depends on its power, that is, on its coverage radius.

The company decided to build exactly two towers in the city. The same equipment goes on both towers, so the two towers have the same coverage radius. For every house to get service, the areas covered by the two towers together must contain every house in the city. To keep the equipment cheap, the coverage radius of the two towers must be as small as possible. The figure below shows two ways to cover a city with ten houses. Both (a) and (b) cover every house, but (b) is the one with the smaller coverage radius.

You are given the location of every house. Write a program that computes the smallest coverage radius of the two towers that still serves every house.

Input

The input holds several test cases. The first line of a test case has the number of houses in the city, NN (3N403 \le N \le 40). Each of the next NN lines has two integers XX and YY (0X1040 \le X \le 10^4, 0Y1040 \le Y \le 10^4) separated by one space, the coordinates of one house. No two houses sit at the same location.

The end of the input is a line that holds a single 00. Do not process that line.

Output

For each test case print one line with the smallest coverage radius of the equipment installed on the two towers. Round the value at the third decimal place and print two decimal places. No input places the answer on a rounding boundary.