PointsGame
SRM 407 · 2008-06-26 · by Gluk
SRM 407 · 2008-06-26 · by Gluk · Dynamic Programming
Problem Statement
Problem Statement
You are given a set of white points on a plane, with the x and y coordinates of the i-th point represented by the i-th elements of pointsX and pointsY, respectively. You play a game with your friend alternating turns. On your turn, you pick any white point and color it red. On his turn, your friend picks any white point and colors it blue. The game ends when there are no white points left, and the final score is the sum of all distances between pairs of points with different colors. Knowing that you make the first turn, and that your opponent plays optimally and wants to minimize the final score, return the highest final score you can achieve.
Notes
- Your return must have relative or absolute error less than 1E-9.
Constraints
- pointsX will contain between 2 and 12 elements, inclusive.
- pointsY will contain the same number of elements as pointsX.
- Each element of pointsX and pointsY will be between 0 and 1000, inclusive.
- All points in the given set will be distinct.
Examples
0)
{0,0}
{0,1}
Returns: 1.0
There are only 2 points and the answer is the distance between them.
1)
{0,0,1,1}
{0,5,0,5}
Returns: 12.198039027185569
Your friend can always choose the closest point to get the smallest answer.
2)
{0,0,0,0}
{0,1,5,6}
Returns: 12.0
3)
{0,1,2,3}
{0,0,0,0}
Returns: 6.0
4)
{245,333}
{245,333}
Returns: 124.45079348883236
Submissions are judged against all 134 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PointsGame with a public method double gameValue(vector<int> pointsX, vector<int> pointsY) · 134 test cases · 2 s / 256 MB per case