Fireflies

There are $n$ fireflies moving in a plane. Firefly $i$ starts at $(x_i, y_i)$ and moves with constant velocity $(a_i, b_i)$. After time $t$ its position is $(x_i + t \cdot a_i, y_i + t \cdot b_i)$.

You want to capture every firefly in one axis-aligned square photo frame. You may choose the shutter time $t$ freely. Find the minimum side length $d$ of a square, with sides parallel to the axes, that can contain all fireflies at some time $t$.

The first line contains an integer $n$ ($1 \le n \le 100\,000$).

Each of the next $n$ lines contains four integers $x_i, y_i, a_i, b_i$ ($-10^6 \le x_i, y_i, a_i, b_i \le 10^6$). $(x_i, y_i)$ is the starting position and $(a_i, b_i)$ is the velocity vector.

Print one real number $d$, the minimum possible side length of an axis-aligned square that covers all fireflies at some time $t$. Your answer is accepted if it differs from the correct value by at most $10^{-3}$ in absolute or relative error.

At any time, compute the span of $x$ coordinates and the span of $y$ coordinates; the needed side length is the larger of the two. The objective over time is convex, so ternary search works.