SegmentCutting
SRM 634 · 2014-08-25 · by lg5293
Problem Statement
You have N distinct points in the plane. The points are labeled 0 through N-1. No three of the points are collinear. For each i, point i lies at (x[i], y[i]).
For each pair of points, we draw the straight line segment that connects them. The value associated with each segment will be the square of its length.
Your task is to draw a line in the plane. The line must not pass through any of the given points. Your score will be the sum of values associated with all segments intersected by your line.
You are given the
Constraints
- x will contain between 2 and 1000 elements, inclusive.
- y will contain the same number of elements as x.
- Each element of x and y will be between -1000 and 1000, inclusive.
- All points will be distinct.
- No three points will be collinear.
{0,3}
{0,4}
Returns: 25
We have two points: (0,0) and (3,4). These two points determine a single segment. The square of its length is 25. Any line that intersects that segment will score 25 points.
{0,0,1,1}
{0,1,0,1}
Returns: 6
Here we have four points in the corners of a unit square. The segments that correspond to its sides are worth 1 each. The segments that correspond to its diagonals are worth 2 each. The largest possible score is 6. This score is achieved by any line that passes through two opposite sides of the square.
{-6, 3, -4}
{2, 0, 5}
Returns: 159
{0, 2,-2, 4,-4, 2,-2, 0}
{1, 2, 2, 4, 4, 6, 6, 5}
Returns: 430
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
{1, 4, 9, 16, 25, 36, 49, 64, 81, 100}
Returns: 94640
Submissions are judged against all 97 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SegmentCutting with a public method long long maxValue(vector<int> x, vector<int> y) · 97 test cases · 2 s / 256 MB per case