I. Infinite Polygon
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an infinite sequence of points $$$p_0, p_1, p_2,\cdots$$$ defined as: $$$$$$ p_0=(1,0), \quad p_1=(1,\frac{1}{2}), \quad p_i=(\frac{1}{i}, \frac{1}{i+1}) \quad \mathrm{for}\ i\geq 1 $$$$$$ The sequence continues indefinitely and approaches the point $$$(0,0)$$$. See the figure in the sample test case for an illustration of the sequence and the polygon $$${\cal P}$$$.

The polygon $$${\cal P}$$$ is created by connecting the points in order with line segments $$$$$$ p_0\rightarrow p_1\rightarrow p_2\rightarrow \cdots $$$$$$ The boundary is completed by adding the segment from $$$(0,0)$$$ to $$$p_0$$$.

Answer $$$q$$$ queries. Each query $$$(n_x, d_x, n_y, d_y)$$$ represents a point $$$$$$ Q =(\frac{n_x}{d_x},\frac{n_y}{d_y} ). $$$$$$ For each query, compute the minimum Euclidean distance from $$$Q$$$ to the region enclosed by $$${\cal P}$$$. Thus, if $$$Q$$$ lies inside or on the boundary of $$${\cal P}$$$, the distance is $$$0$$$.

Input
  • The first line contains a single integer $$$q$$$ ($$$1\leq q\leq 2\times 10^5$$$), the number of queries.
  • $$$q$$$ lines follow, each line containing four integers $$$n_x, d_x, n_y, d_y$$$ ($$$-10^2\leq n_x, n_y\leq 10^2$$$, $$$1\leq d_x, d_y\leq 10^6$$$), describing the query point $$$Q$$$.
Output

$$$q$$$ lines. The $$$i$$$-th line should contain your answer for the $$$i$$$-th query. Your answer will be accepted if its absolute or relative error is at most $$$10^{-6}$$$.

Note on Precision: This problem involves floating-point computations. Although answers with absolute or relative error at most $$$10^{-6}$$$ are accepted, using higher-precision floating point types (such as long double in C++) is recommended.
Example
Input
13
9 10 1 4
1 2 -1 5
1 1 1 3
3 4 1 2
6 5 1 5
-1 10 0 1
-1 10 -1 10
1 100 1 100
38 1 1 1
-71 75 44 851407
-79 839169 35 925573
38 406091 44 579238
-72 71073 49 159480
Output
0
0.2
0
0.079056941
0.2
0.1
0.141421356
0.0000707071
37.003378224
0.9466666681
0.0001014515
0
0.0010586112
Note

Refer to the figure below for an illustration. This visualization includes the first four query points: $$$Q_1 = (\frac{9}{10}, \frac{1}{4})$$$, $$$Q_2 = (\frac{1}{2}, \frac{1}{5})$$$, $$$Q_3 = (1, \frac{1}{3})$$$ and $$$Q_4 = (\frac{3}{4},\frac{1}{2})$$$.

Illustration of polygon $$${\cal P}$$$ and query points $$$Q_1$$$, $$$Q_2$$$, $$$Q_3$$$ and $$$Q_4$$$. $$$O$$$ denotes the point $$$(0,0)$$$. Thick lines denote the illustrated portion of the boundary of polygon $$${\cal P}$$$. Query points $$$Q_1, Q_2, Q_3, Q_4$$$ are marked with an X. The minimum Euclidean distance to $$${\cal P}$$$ for each point is illustrated by thin lines.
  • Point $$$Q_1$$$ is inside $$${\cal P}$$$, so output $$$0$$$.
  • Point $$$Q_2$$$ is nearest to the segment from $$$(0,0)$$$ to $$$p_0$$$, with a distance of $$$0.20$$$ units.
  • Point $$$Q_3$$$ lies on segment $$$p_0p_1$$$, hence the answer is $$$0$$$.
  • Point $$$Q_4$$$ has a distance of approximately $$$0.0791$$$ units from segment $$$p_1p_2$$$, which is the minimum distance to $$${\cal P}$$$.