{"raw_statement":[{"iden":"statement","content":"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.\n\nThe task is complicated by the fact that Oz has $n$ satellites revolving around it. For each satellite, its polar coordinates $(rho_i \\; phi.alt_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 $phi.alt_i$ is the polar angle between the satellite and some fixed reference direction measured in arc seconds.\n\nAssume that Elphaba is located in the point denoted by vector $arrow(r)$ and has mass $m$, while $i$-th satellite is located in the point denoted by vector $arrow(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, $| arrow(r) -arrow(r)_i |^2$. Thus, exact value of force $arrow(F)_i$ applied to Elphaba by $i$-th satellite is as follows:\n\n$$\\vec F_i = -\\dfrac{Gmm_i(\\vec r - \\vec r_i)}{|\\vec r - \\vec r_i|^3}$$\n\nHere, $G$ is the universal gravitational constant, the value of which does not concern us in this problem.\n\nForces applied from different satellites sum up directly. Therefore, the overall force $arrow(F)$ applied to Elphaba by all satellites is equal to $arrow(F) = arrow(F)_1 + \\\\dots + arrow(F)_n$.\n\nElphaba 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 $arrow(F)$ must be collinear to $arrow(r)$ for all points $arrow(r)$ on Elphaba's trajectory.\n\nYour task is to find all possible directions for Elphaba's flight.\n\nThe first line of input contains a single *even* integer $n$ ($2 <= n <= 2 dot.op 10^5$), the number of satellites.\n\nEach of the following $n$ lines contains three integers $rho_i$, $phi.alt_i$, and $m_i$ ($1 <= rho_i <= 10^(18)$, $0 <= phi.alt_i < 129 thin 600$, $1 <= m_i <= 10^9$) representing polar coordinates and mass of the $i$-th satellite.\n\nIt is guaranteed that no two satellites have the same polar angle $phi.alt$.\n\nOutput a sorted list of real numbers $alpha$ ($0 <= alpha < 129 thin 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 dot.op 10^5$ directions.\n\nOne 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^compose$). Therefore, $60\\\"= 1 '$, $60 ' = 1^compose$, and $129 thin 600\\\"= 360^compose$, which means that $129 thin 600$ arc seconds constitute the full arc.\n\nIn 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 $arrow(r)_1$ and $arrow(r)_2$ having polar angles $90^compose = 32 thin 400\\\"$ and $270^compose = 97 thin 200\\\"$ correspondingly.\n\n"},{"iden":"input","content":"The first line of input contains a single *even* integer $n$ ($2 <= n <= 2 dot.op 10^5$), the number of satellites.Each of the following $n$ lines contains three integers $rho_i$, $phi.alt_i$, and $m_i$ ($1 <= rho_i <= 10^(18)$, $0 <= phi.alt_i < 129 thin 600$, $1 <= m_i <= 10^9$) representing polar coordinates and mass of the $i$-th satellite.It is guaranteed that no two satellites have the same polar angle $phi.alt$."},{"iden":"output","content":"Output a sorted list of real numbers $alpha$ ($0 <= alpha < 129 thin 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 dot.op 10^5$ directions."},{"iden":"note","content":"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^compose$). Therefore, $60\\\"= 1 '$, $60 ' = 1^compose$, and $129 thin 600\\\"= 360^compose$, which means that $129 thin 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 $arrow(r)_1$ and $arrow(r)_2$ having polar angles $90^compose = 32 thin 400\\\"$ and $270^compose = 97 thin 200\\\"$ correspondingly."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be an even integer, $ n \\geq 2 $.  \nFor each $ i \\in \\{1, \\dots, n\\} $, let $ (\\rho_i, \\phi_i, m_i) \\in \\mathbb{R}^+ \\times [0, 129600) \\times \\mathbb{R}^+ $ denote the polar radius, polar angle (in arc seconds), and mass of the $ i $-th satellite.  \nLet $ \\vec{r}_i \\in \\mathbb{R}^2 $ be the position vector of the $ i $-th satellite in Cartesian coordinates:  \n$$\n\\vec{r}_i = \\rho_i \\cdot \\left( \\cos\\left( \\frac{\\pi \\phi_i}{129600} \\right), \\sin\\left( \\frac{\\pi \\phi_i}{129600} \\right) \\right)\n$$  \nLet $ \\vec{r} \\in \\mathbb{R}^2 \\setminus \\{ \\vec{r}_1, \\dots, \\vec{r}_n \\} $ be the position vector of Elphaba.  \n\nThe gravitational force exerted on Elphaba (of mass $ m $) by the $ i $-th satellite is:  \n$$\n\\vec{F}_i = -\\frac{G m m_i (\\vec{r} - \\vec{r}_i)}{|\\vec{r} - \\vec{r}_i|^3}\n$$  \nThe total force is:  \n$$\n\\vec{F} = \\sum_{i=1}^n \\vec{F}_i\n$$  \n\n**Constraint**  \nElphaba’s trajectory is a straight line through the origin (Oz) in direction $ \\vec{r} = \\lambda \\vec{d} $, $ \\lambda > 0 $, where $ \\vec{d} \\in \\mathbb{R}^2 $ is a unit direction vector.  \nThe force $ \\vec{F} $ must be **collinear** with $ \\vec{r} $ for **all** $ \\lambda > 0 $, i.e.,  \n$$\n\\vec{F} \\parallel \\vec{r} \\quad \\forall \\lambda > 0\n$$  \nThis implies $ \\vec{F} \\times \\vec{r} = \\vec{0} $ (cross product in 2D: scalar $ F_x r_y - F_y r_x = 0 $).  \n\n**Objective**  \nFind all polar angles $ \\alpha \\in [0, 129600) $ (in arc seconds) such that if Elphaba flies along the ray at angle $ \\alpha $, then $ \\vec{F} \\parallel \\vec{r} $ for all $ \\vec{r} $ on that ray.  \n\nEquivalently, define the unit direction vector:  \n$$\n\\vec{d} = \\left( \\cos\\theta, \\sin\\theta \\right), \\quad \\theta = \\frac{\\pi \\alpha}{129600}\n$$  \nThen $ \\vec{r} = \\lambda \\vec{d} $, and the condition becomes:  \n$$\n\\sum_{i=1}^n \\frac{m_i (\\vec{r}_i - \\vec{r})}{|\\vec{r}_i - \\vec{r}|^3} \\parallel \\vec{d} \\quad \\forall \\lambda > 0\n$$  \n\nThis condition holds **iff** the component of the total force perpendicular to $ \\vec{d} $ vanishes for all $ \\lambda > 0 $.  \nDue to radial symmetry and the requirement holding for all $ \\lambda $, the only possible directions $ \\vec{d} $ are those for which the **vector sum of the satellite contributions, projected perpendicularly to $ \\vec{d} $, is identically zero** for all $ \\lambda $.  \n\nIt can be shown (via symmetry and cancellation) that this occurs **iff** the set of satellites is symmetric with respect to the line through the origin in direction $ \\vec{d} $.  \nSince $ n $ is even and no two satellites share the same angle, the only possible solutions are directions $ \\alpha $ such that for every satellite at $ (\\rho_i, \\phi_i, m_i) $, there exists a satellite at $ (\\rho_j, \\phi_j, m_j) $ with:  \n$$\n\\phi_j = \\phi_i + 180^\\circ \\mod 360^\\circ \\quad \\text{and} \\quad m_j = m_i, \\quad \\rho_j = \\rho_i\n$$  \ni.e., diametrically opposite with equal mass.  \n\nThus, the possible flight directions $ \\alpha $ are the **bisectors** of all such symmetric pairs.  \n\nLet $ S $ be the set of all $ \\phi_i $.  \nPartition the satellites into unordered pairs $ \\{i, j\\} $ such that $ \\phi_j \\equiv \\phi_i + 64800 \\pmod{129600} $ and $ m_i = m_j $, $ \\rho_i = \\rho_j $.  \nFor each such pair, the direction bisecting them is:  \n$$\n\\alpha = \\frac{\\phi_i + \\phi_j}{2} \\mod 129600\n$$  \nSince $ \\phi_j = \\phi_i + 64800 $, then:  \n$$\n\\alpha = \\phi_i + 32400 \\mod 129600\n$$  \nThus, for each symmetric pair, there is **one** valid direction: $ \\alpha = \\phi_i + 32400 \\mod 129600 $.  \n\n**Output**  \nThe set of all such $ \\alpha $, sorted in ascending order.  \n\n**Final Formal Statement**  \n\n**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be even, $ 2 \\leq n \\leq 2 \\cdot 10^5 $.  \nLet $ \\mathcal{S} = \\{ (\\rho_i, \\phi_i, m_i) \\}_{i=1}^n $, with $ \\rho_i > 0 $, $ \\phi_i \\in [0, 129600) $, $ m_i > 0 $, and all $ \\phi_i $ distinct.  \n\n**Constraint**  \nThe satellites form $ n/2 $ symmetric pairs: for each $ i $, there exists a unique $ j \\ne i $ such that:  \n$$\n\\phi_j \\equiv \\phi_i + 64800 \\pmod{129600}, \\quad \\rho_j = \\rho_i, \\quad m_j = m_i\n$$  \n\n**Objective**  \nCompute the set:  \n$$\n\\mathcal{A} = \\left\\{ \\left( \\phi_i + 32400 \\right) \\mod 129600 \\;\\middle|\\; \\text{for each symmetric pair } (\\phi_i, \\phi_j) \\right\\}\n$$  \nOutput $ \\mathcal{A} $ sorted in ascending order.","simple_statement":"Elphaba wants to fly in a straight line from Earth (at origin) to infinity without being pulled off course by satellites. Each satellite pulls her with a gravitational force. She can only fly in directions where the total gravitational force from all satellites always points exactly along her flight path — meaning the force is parallel to her position vector at every point.\n\nYou’re given n satellites in polar coordinates (rho, phi, mass). Find all possible flight directions (angles in arc seconds) such that the net gravitational force on Elphaba is always collinear with her position vector along that ray.\n\nOutput all such angles in sorted order, between 0 and 129600 arc seconds (full circle).","has_page_source":false}