406316: GYM102354 H Defying Gravity

Planet Oz is located in the origin of two-dimensional euclidean space. Elphaba wants to show everyone that her powers lie far beyond the laws of physics. To do this, she wants to take off from Oz and fly away along some straight line to infinity and beyond.

The task is complicated by the fact that Oz has $$$n$$$ satellites revolving around it. For each satellite, its polar coordinates $$$(\rho_i; \varphi_i)$$$ and mass $$$m_i$$$ are known. Here, the planet and satellites are considered points, $$$\rho_i$$$ is the radial distance from Oz to the $$$i$$$-th satellite, and $$$\varphi_i$$$ is the polar angle between the satellite and some fixed reference direction measured in arc seconds.

Assume that Elphaba is located in the point denoted by vector $$$\vec r$$$ and has mass $$$m$$$, while $$$i$$$-th satellite is located in the point denoted by vector $$$\vec r_i$$$. The satellite attracts Elphaba with the force directed from Elphaba to the satellite. This force is proportional to Elphaba's mass $$$m$$$ and satellite's mass $$$m_i$$$, and inversely proportional to the squared distance between them, $$$|\vec r - \vec r_i|^2$$$. Thus, exact value of force $$$\vec F_i$$$ applied to Elphaba by $$$i$$$-th satellite is as follows:

$$$$$$\vec F_i = -\dfrac{Gmm_i(\vec r - \vec r_i)}{|\vec r - \vec r_i|^3}$$$$$$

Here, $$$G$$$ is the universal gravitational constant, the value of which does not concern us in this problem.

Forces applied from different satellites sum up directly. Therefore, the overall force $$$\vec F$$$ applied to Elphaba by all satellites is equal to $$$\vec F = \vec F_1 + \dots + \vec F_n$$$.

Elphaba wants to choose the direction of her flight in such a way that it doesn't pass through any of the satellites, and its direction is not affected by satellites at any moment of time. In other words, the force $$$\vec F$$$ must be collinear to $$$\vec r$$$ for all points $$$\vec r$$$ on Elphaba's trajectory.

Your task is to find all possible directions for Elphaba's flight.

The first line of input contains a single even integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$), the number of satellites.

Each of the following $$$n$$$ lines contains three integers $$$\rho_i$$$, $$$\varphi_i$$$, and $$$m_i$$$ ($$$1 \leq \rho_i \leq 10^{18}$$$, $$$0 \leq \varphi_i < 129\,600$$$, $$$1 \leq m_i \leq 10^9$$$) representing polar coordinates and mass of the $$$i$$$-th satellite.

It is guaranteed that no two satellites have the same polar angle $$$\varphi$$$.

Output a sorted list of real numbers $$$\alpha$$$ ($$$0 \leq \alpha < 129\,600$$$) denoting polar angles in arc seconds of all possible flight directions. Your answer would be considered correct if absolute or relative error of every number in the list is at most $$$10^{-6}$$$. It is guaranteed that the answer always contains at most $$$2 \cdot 10^{5}$$$ directions.

2
1 0 1
1 64800 1

2
32400.0000000
97200.0000000

One arc second (denoted as $$$1"$$$) is equal to one sixtieth of one arc minute (denoted as $$$1'$$$), which in turn is equal to one sixtieth of one arc degree (denoted as $$$1^\circ$$$). Therefore, $$$60" = 1'$$$, $$$60'=1^\circ$$$, and $$$129\,600"=360^\circ$$$, which means that $$$129\,600$$$ arc seconds constitute the full arc.

In the first example, the first satellite is located at point $$$A(1;0)$$$, and the second one is located at point $$$B(-1;0)$$$. The only possible flight directions on the picture are denoted by $$$\vec r_1$$$ and $$$\vec r_2$$$ having polar angles $$$90^\circ=32\,400"$$$ and $$$270^\circ=97\,200"$$$ correspondingly.