Description

The isolation shield is an important component that is used to prevent other cosmic rays from damaging the scanner (not the tractor!) as much as possible.

Simply, we can regard the uncut isolation shield as a unit sphere surface, as shown in the figure below.

The work plan requires completing $N$ ($1 \le N \le {10}^6$) observation tasks.

For the $i$-th observation, we start from point $(0,0)$ and scan an asteroid centered at $(x_i,y_i,z_i)$ with radius $r_i$ ($-{10}^6 < x_i,y_i < {10}^6$，$0 < r_i < z_i < {10}^6$).
Here we can simply treat the asteroid as a solid sphere.

For each observation, we must ensure that we can scan the whole asteroid through the hole cut on the shield.

Now please compute the radius of the circular hole on the spherical surface (the length of a great-circle arc), i.e., the minimum enclosing circle (the “circle” is on the curved surface) that covers the union of the projections of all asteroid spheres onto the upper unit hemisphere.

Since it is a unit sphere, this value should equal half of the plane angle formed by the lines from the sphere center to the two endpoints of the hole’s diameter.

Clearly, this angle is less than $\frac{\pi}{2}$ and greater than $0$. If the angle is $\omega$ rad, please output $\frac{\omega}{\pi/2} \times {10}^5$ and round down.

Input Format

The first line contains an integer $N$, meaning there are $N$ observation plans.

Each of the following lines contains four integers separated by spaces, in order: $x_i,y_i,z_i,r_i$.

Output Format

Output an integer in the range $[0, 99999]$.

5
30 10 10 9
100 -10 100 50
-30 100 50 30
12 42 64 20
287 123 46 31

67877

Hint

Sample Explanation

The figure below shows the circles formed by projecting each asteroid onto the shield, and a sketch of the final circular hole to be cut.

Hint

• This is not a computer graphics problem.
• All characters, times, events, and text in the background story are fictional.
• The input is large; it is recommended to use faster input/output methods.
• Please make full use of your algebra knowledge.

Source

From the 2021 Tsinghua University Student Programming Contest and Collegiate Invitational (THUPC2021).

Resources such as editorials can be found at https://github.com/yylidiw/thupc_2/tree/master.

Translated by ChatGPT 5