P7612 [THUPC 2021] Stars

**Seeking the stars of the Olympiad** —— Jing (in the 7th year of Jian’an (A.D. 0202)). > “On a certain year, month, and day, there were two close friends, named Jing and Ao, who sought the secrets of the stars. At first they suffered from having nothing to use, then they suffered from gaining nothing. Later chaos came; Ao moved away, and his whereabouts became unknown. Can such a small body really look up to fate? Indeed, their feelings are lamentable. I wrote this to record it.” > —— *Record of Mars* . In Cosmic Era 1024, Solar Year 256, Earth Day, in the Strophas star system, the “Hershisaki” asteroid mining area, aboard the advanced mining ship “Gigak”. Captain Kuro was reading the *Record of Mars* written thousands of years ago. It has been verified as humanity’s first formal observation record of the starry sky with a scientific purpose. However, a rapid alarm from the system interrupted him. “Manual damage to the auxiliary traction bay isolation shield,” a crew member wrote in the damage-control notes of the system. “Our lovely princess Konada dragged another huge rock over and cracked the shield, and said she wanted to give it to that kid Makana.” Konada is the captain’s daughter, and Maka is the first mate’s son. They can probably be considered childhood friends. Captain Kuro’s headache returned. This was already the third time. Last time, the maintenance department warned that there were no spare isolation shields of the current model. “You’d better not blame the lovely Konada,” said the maintenance team leader. “But we could try using those non-rotating ones to make a substitute. I just can’t figure out how big a hole to cut.” As a member of the main-brain data team, Captain Kuro asks you to help the maintenance department compute the minimum hole size that must be cut.

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.

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 an integer in the range $[0, 99999]$.

**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](https://github.com/yylidiw/thupc_2/tree/master). Translated by ChatGPT 5