MarblePositioning
SRM 579 · 2012-12-13 · by vexorian
SRM 579 · 2012-12-13 · by vexorian · Brute Force, Geometry, Search
Problem Statement
Problem Statement
NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.
Everybody loves geometry, so here is a geometry problem. You have a few marbles of possibly different sizes. You are given aint[] radius that describes the marbles: each element of radius is the radius of one of your marbles.
You want to place all marbles onto a straight line that is drawn on the table. Clearly, this makes the problem two-dimensional: we can just view the marbles as circles that will all be touching the line from above. Of course, the marbles cannot overlap, so in our problem no two circles are allowed to overlap. Note that you may place the marbles onto the line in any order, you do not have to preserve the order in which they are given in radius.
Additionally, you want to pack the bottoms of the marbles as close together as possible. More precisely: For each marble consider the point where it touches the line. Compute and return the smallest possible distance between the farthest two of those points. (That is, if you imagine the line as going from the left to the right, your task is to minimize the distance between the leftmost and the rightmost of the points where the circles touch the line.)
Everybody loves geometry, so here is a geometry problem. You have a few marbles of possibly different sizes. You are given a
You want to place all marbles onto a straight line that is drawn on the table. Clearly, this makes the problem two-dimensional: we can just view the marbles as circles that will all be touching the line from above. Of course, the marbles cannot overlap, so in our problem no two circles are allowed to overlap. Note that you may place the marbles onto the line in any order, you do not have to preserve the order in which they are given in radius.
Additionally, you want to pack the bottoms of the marbles as close together as possible. More precisely: For each marble consider the point where it touches the line. Compute and return the smallest possible distance between the farthest two of those points. (That is, if you imagine the line as going from the left to the right, your task is to minimize the distance between the leftmost and the rightmost of the points where the circles touch the line.)
Notes
- The returned values must have an absolute or relative error less than 1e-9.
Constraints
- radius will contain between 2 and 8 elements, inclusive.
- Each element of radius will be between 1 and 1000000000 (10^9), inclusive.
Examples
0)
{1, 2}
Returns: 2.8284271247461903
One of the best ways to place the marbles is the following one:
1)
{1,1000000000}
Returns: 63245.553203367585
2)
{7,7,7}
Returns: 28.0
3)
{1,2,3,4,5,6,7,8}
Returns: 50.58155219373389
4)
{1000000000,200000000,300000000,400000000,500000000,600000000,700000000,800000000}
Returns: 6.53173138056799E9
Submissions are judged against all 154 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MarblePositioning with a public method double totalWidth(vector<int> radius) · 154 test cases · 2 s / 256 MB per case