Fat Ninjas

Interview

Time limit3sMemory limit128 MB

Summary

Given point sensors in an N by N square, find the diameter of the largest circle that can travel from the left side to the right side without touching any sensor.

Level: Hard8 of 10
Topics: Geometry, Union-find, Binary search, Graph
Solved: No attempts yet

Problem

A downturn in the contract-killing market has left many ninjas unemployed, sitting at home eating hamburgers and watching game shows. Having grown overweight, they are drawn to a game show that offers a lifetime supply of hamburgers to anyone who can use ninja-like stealth to cross a square hall without triggering any of the strategically placed laser sensors.

The hall is a square region measuring $N \times N$ metres. Each laser is mounted on the ceiling and shoots a beam straight down to a sensor on the floor; a beam has zero width and sets off the alarm if a contestant touches its sensor. A contestant must enter from the left side of the hall, move their entire body across, and pass completely through the right side, without ever crossing the top or bottom walls. Merely touching the right side is not enough.

The host wants to place the sensors so that very fat ninjas find it hard to succeed. Given an arrangement of sensors, compute the girth (diameter) of the fattest ninja that can still cross the hall. Assume each ninja is a perfect circle when viewed from above, and that ninjas are too heavy to jump off the floor.

Input

The input contains several game instances. Each instance begins with a line containing two integers $N$ and $L$ separated by a single space: $N$ is the length of the hall's side in metres and $L$ is the number of installed lasers ( $1 \le N, L \le 1000$ ). Each of the next $L$ lines contains two integers $x$ and $y$ separated by a single space, the coordinates of a laser sensor on the floor ( $0 \le x, y \le N$ ).

A line containing two zeros terminates the input and must not be processed.

Output

For each game, output on its own line a single floating-point number: the girth (diameter) of the fattest ninja that can move through the hall without touching any laser sensor. Round the diameter to exactly three decimal places, padding with zeros if necessary.

Rounding rule for a positive value $R.xxxy$ : if the fourth decimal digit $y$ is less than $5$ , the result is $R.xxx$ ; otherwise the result is $R.xxx + 0.001$ . For example, $10.3463$ is written as $10.346$ , and $10.3695$ is written as $10.370$ .

Examples5

Example 1

Input

Expected output

3.000
2.828

Example 2
Input
```
10 1
5 5
0 0
```
Expected output
```
5.000
```
Example 3
Input
```
10 1
3 2
0 0
```
Expected output
```
8.000
```
Example 4
Input
```
10 2
5 3
5 7
0 0
```
Expected output
```
4.000
```
Example 5
Input
```
6 2
3 2
5 4
0 0
```
Expected output
```
2.828
```