EquilibriumPoints
SRM 421 · 2008-10-07 · by ivan_metelsky
Problem Statement
There are N points situated on a straight line. The i-th point is located at coordinate x[i] and has a mass of m[i]. The locatıon of each point is strongly fixed and cannot be changed by any forces. Coordinates of all points are distinct.
When another point P is added on the line and its position is not fixed, the point falls under the impact of gravitational forces from each of the given N points. Points located to the left of P force it to the left, and points located to the right of P force it to the right. When two points are located a distance of d apart and have masses m1 and m2, the value of gravitational force between them is F = G * m1 * m2 / d^2, where G is some positive constant.
Point P is said to be an equilibrium point if the vector sum of gravitational forces from all points on P equals zero. In other words, the sum of the values of gravitational forces between P and all the points located to the left of P must be the same as the sum of the values of gravitational forces between P and all the points located to the right of P.
It is known that there always exist exactly N-1 equilibrium points. Return a
Notes
- Each element of your return value must have an absolute or relative error less than 1e-9.
- You don't need to know the mass of point P and the value of constant G to solve the problem.
Constraints
- x will contain between 2 and 50 elements, inclusive.
- m will contain the same number of elements as x.
- Each element of x will be between 1 and 1000, inclusive.
- Each element of m will be between 1 and 1000, inclusive.
- x will be sorted in strictly ascending order.
{1, 2}
{1, 1}
Returns: {1.5 }
When two points have the same mass, the equilibrium point is located exactly halfway between them.
{1, 2}
{1, 1000}
Returns: {1.0306534300317156 }
When two points have distinct masses, the equlibrium point is located closer to the point with lesser mass.
{1, 2, 3}
{1, 2, 1}
Returns: {1.4060952084922507, 2.5939047915077493 }
There are two equilibrium points located symmetrically with respect to the middle point of the input points.
{2, 3, 5, 7}
{3, 2, 7, 5}
Returns: {2.532859446114924, 3.7271944335152813, 6.099953640852538 }
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}
{1,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}
Returns: {1.0243592979720102, 2.4723232132703723, 3.485989792537662, 4.490809221844989, 5.4932617175765674, 6.494748386875358, 7.495748181372663, 8.49646878737487, 9.497014740550618, 10.497444372482867, 11.497792802126018, 12.498082448803473, 13.498328310343044, 14.498540813865308, 15.498727448906457, 16.498893749610183, 17.499043910210922, 18.499181184652592, 19.499308154336234, 20.499426912745825, 21.49953919630081, 22.499646479702527, 23.49975004751252, 24.499851049756472, 25.49995054692714, 26.500049548271605, 27.50014904636143, 28.500250050473525, 29.500353621162304, 30.50046090855136, 31.500573197343506, 32.50069196243575, 33.50081894051381, 34.5009562254225, 35.50110639905401, 36.501272716027586, 37.501459371520454, 38.5016719010186, 39.50191779601607, 40.50220748657395, 41.50255597509482, 42.502985688330185, 43.50353175794686, 44.50425253876912, 45.50525261274612, 46.50673976958521, 47.5091932332803, 48.51401504075508, 49.52769061786695 }
Submissions are judged against all 105 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EquilibriumPoints with a public method vector<double> getPoints(vector<int> x, vector<int> m) · 105 test cases · 2 s / 256 MB per case