SegmentCutting | Topcoder Archive

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 int[]s x and y with N elements each: the coordinates of the given points. Compute and return the largest score you can achieve.

Definition

Class:: SegmentCutting
Method:: maxValue
Parameters:: int[], int[]
Returns:: long
Method signature:: long maxValue(int[] x, int[] y)
(be sure your method is public)

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.

Examples

```
{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

{-24,11,-235,49,13,-247,-575,80,35,29,1,-9,-1,-1,-27,-3,-20,13,-33,111,
-36,30,-303,-645,-23,-5,393,227,89,145,6,515,234,271,-901,239,-368,-642,
-3,125,-63,2,221,-113,1,6,3,-31,-6,-49,-785,314,363,-2,34,15,465,11,32,
-72,394,20,-8,-448,429,-7,-88,-11,-42,-8,2,-707,-231,-143,76,-10,-152,
-66,24,-73,778,-29,807,-63,722,-804,413,-21,-2,-131,26,3,-23,101,-551,
-58,21,180,-15,-88,410,604,74,956,62,275,-352,-93,291,184,70,564,-594,
-101,-391,18,115,-329,8,-4,-218,77,218,-145,27,-34,598,-87,-243,-323,34,
211,7,-145,-49,528,-13,10,-778,184,-65,101,-232,503,-6,69,553,-14,25,26,
854,955,-10,-490,-674,-4,9,-373,42,-121,-528,67,-32,23,74,81,-752,-7,
-122,-464,-174,-722,46,961,57,-105,269,48,64,-585,-107,641,9,27,297,5,
-44,107,-600,113,468,-24,-104,277,10,5,75,106,-591,38}

{-1,-2,62,-8,-1,28,-47,241,-10,-3,3,-41,1,95,111,-4,-114,503,1,19,3,
-26,615,762,7,-52,399,-174,-987,30,-49,165,67,551,-214,-36,-108,-242,
-967,69,698,-120,-298,20,-43,32,-171,2,-9,8,50,948,-2,-30,-3,53,-411,
410,141,-8,292,41,71,-523,-329,-284,8,84,34,559,-160,2,73,12,276,-16,
-33,-63,119,869,127,47,963,-7,-995,146,-161,775,17,-5,-167,-315,59,
-345,10,766,-10,-6,850,12,-5,-17,295,-89,14,71,-11,-305,13,-524,181,
-279,-11,15,437,349,20,10,-749,82,25,336,-6,-794,-944,895,-52,72,198,
194,-988,641,-59,-434,-524,-381,368,6,-14,125,-55,319,-666,-610,-274,
359,-39,206,28,-719,-150,51,-366,-341,89,13,-635,-287,56,35,665,103,-81,
156,-4,888,-48,96,-48,340,61,396,272,-16,335,219,-388,15,324,24,-194,9,
-310,7,-25,5,39,-342,118,-92,425,-336,796,950,-419,-812,-488,428,-32,-9}

Returns: 5887914054

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.