Catching Mice

Time limit2sMemory limit128 MB

Summary

Given moving mice with initial positions and velocities, find the largest square cage side length for which no drop time can enclose all mice simultaneously.

Level: Medium6 of 10
Topics: Geometry, Binary search, Math
Solved: No attempts yet

Problem

Robot mice are moving on a large two-dimensional board. A player may move a square cage of side length L to any position on the board and drop it. The cage must stay parallel to the coordinate axes and cannot be rotated.

Each mouse has an initial position and a constant velocity. The cage may be dropped at any time after the game starts. A mouse is caught only if it is completely inside the cage. A mouse on the boundary is not considered caught.

Find the largest L for which it is impossible to catch all mice at once.

Input

The first line contains the number of mice N, where 2 <= N <= 50.

Each of the next N lines contains one mouse's initial position and velocity as px py vx vy. Every value is an integer whose absolute value is at most 1,000. If the initial position is (px, py) and the velocity is (vx, vy), then after t seconds the mouse is at (px + vx * t, py + vy * t).

Output

Print the answer on one line. An absolute or relative error of at most 10^-9 is accepted.

Examples6

Example 1
Input
```
2
0 0 10 0
10 10 -10 0
```
Expected output
```
10.0
```
Example 2
Input
```
3
0 0 1 4
10 0 -6 5
0 10 4 -4
```
Expected output
```
3.0
```

Example 3

Input

4
50 -10 -5 40
10 30 -10 -10
30 20 -15 -1
15 40 -5 -50

Expected output

40.526315789473685

Example 4

Input

Expected output

10.0

Example 5

Input

5
13 20 4 1
50 20 50 1
100 -150 41 1
40 -40 -41 3
-100 63 -79 -1

Expected output

212.78688524590163

Example 6
Input
```
2
0 0 5 3
10 0 5 3
```
Expected output
```
10.0
```