Problem J
Maddison's Square Garden
Maddison and her friends live and work on the perimeter of a unit square with bottom left corner at $(0, 0)$ and top right corner at $(1, 1)$. They’ve decided to build a square community garden centered at $(0.5, 0.5)$, but they can’t decide how big it should be! The garden can’t rotate, so a garden of side length $\ell $ has corners at $(0.5 \pm \frac{\ell }{2}, 0.5 \pm \frac{\ell }{2}).$
It takes longer to walk through the garden compared to the open space that exists right now, and each of Maddison’s friends have a limit as to how long they are willing to walk to work. They each walk at $0.1$ units per minute in the open space or on the perimeter of the garden, but $0.1 \cdot \delta $ units per minute through the garden.
Maddison’s friends are also very stubborn. They will always walk in a straight line from home to work, no matter how much the garden slows them down.
Find the largest side length $0 \leq \ell \leq 1$ of a square garden centered at $(0.5, 0.5)$ such that all of Maddison’s friends can still get to work on time.
Input
The first line of input contains integer $N$ ($1 \leq N \leq 10^5$) and real number $\delta $ ($0 < \delta \leq 1$). Then $N$ lines follow, each containing five real numbers $x_ h, y_ h, x_ w, y_ w, t$ where $(x_ h, y_ h)$ and $(x_ w, y_ w)$ are points denoting the home and workplace respectively of one of Maddison’s friends and $0 \leq t \leq 120$ is the maximum number of minutes that friend is willing to take to walk between their home and workplace. The points $(x_ h, y_ h)$ and $(x_ w, y_ w)$ are always on the perimeter of the unit square. All real numbers are given with exactly 6 digits of precision after the decimal.
It is guaranteed that all of Maddison’s friends can get to work on time when there is no garden.
Output
Output a single floating-point value $\ell $ ($0 \leq \ell \leq 1$) that is the maximum valid side length of Maddison’s Square Garden. Your answer will be considered correct if it is within an absolute error of $10^{-6}$ of the correct answer.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 0.500000 0.300000 0.000000 0.900000 0.000000 10.000000 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
1 0.500000 0.300000 0.000000 1.000000 0.600000 15.000000 |
0.7589706801981031 |
| Sample Input 3 | Sample Output 3 |
|---|---|
1 0.500000 0.300000 0.000000 0.900000 1.000000 15.000000 |
0.3396795414266122 |
