410554: GYM104049 F Neodymium Gravity

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Neodymium Gravitytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

NASA has been exploring the galaxy and they've found a very interesting celestial arrangement. They hope to study it further by placing an observation station.

They have found $$$N$$$ neodymium spheres arranged at distinct points along a straight line. Each of these spheres can be described as a location $$$l_i$$$ and a mass $$$m_i$$$.

Given the high mass of these spheres, NASA's observation satellites will be accelerated by gravity towards sphere $$$i$$$ according to the formula $$$\frac{g m_i}{r^2}$$$, where $$$g$$$ is the gravitational constant and $$$r$$$ is the distance between the satellite and sphere. For some strange, unexplained reason the spheres themselves are guaranteed to never move.

NASA wants to place its observation satellites in stable locations (where the gravitational forces should cancel out). Specifically, they would like to know every stable location (besides where the spheres themselves are located).

Given the mass and locations of all the spheres, tell NASA all the stable points, listed in increasing order. You can assume that the radius of the spheres is negligible and forces from objects outside this formation are also negligible.

Input

The first line will contain a single integer $$$2 \leq N \leq 500$$$.

The next $$$N$$$ lines contain a pair of integers, the location $$$l_i$$$, followed by the mass, $$$m_i$$$ ($$$1 \leq l_i, m_i \leq 5000$$$).

Output

A list of all stable points, in increasing order. Answers within $$$10^{-6}$$$ will be tolerated.

ExampleInput
3
1 1
4 8
2 1
Output
1.46165446
2.54537408

加入题单

算法标签: