SecondDiameters | Topcoder Archive

Problem Statement

In this problem the distance d(A,B) between two points in the plane is the standard Euclidean distance: sqrt( (A.x-B.x)^2 + (A.y-B.y)^2 ).

Given a set of points S, the distance set is the set D(S) = { d(A,B) : A, B belong to S }. For example, given the set S = { (0,0), (1,0), (1,1) } the distance set D(S) is { 0, 1, sqrt(2) }.

The second diameter of a set of two or more points is the second largest value in its distance set. For example, for the set S mentioned above the second diameter is 1.

You are given are N distinct points in the plane. Points are numbered from 0 to N-1. Point i is located at (X[i], Y[i]).

Let S[i] be the set of all of these points except point i. Let ans[i] be the square of the second diameter of S[i]. Return sum(ans).

Definition

Class:: SecondDiameters
Method:: getSecondDiameters
Parameters:: int[], int[]
Returns:: long
Method signature:: long getSecondDiameters(int[] X, int[] Y)
(be sure your method is public)

Notes

Note that the distance set is a simple set and not a multiset, so the second diameter is never equal to the diameter, even if there are multiple pairs of points that have a distance equal to the diameter.

Constraints

X will contain between 3 and 2000 elements, inclusive.
Y will contain the same number of elements as X.
Each number in the input will be between 0 and 9999, inclusive.
All points described by X and Y will be distinct.

Examples

```
{0, 1, 1}
```
```
{0, 0, 1}
```
```
Returns: 0
```
The three points from the problem statement. We have D( S[0] ) = D( S[2] ) = {0, 1} and D( S[1] ) = {0, sqrt(2)}. In all cases the second largest distance is zero.
```
{0, 0, 1, 1}
```
```
{0, 1, 0, 1}
```
```
Returns: 4
```
Four points in the corners of a unit square. Regardless of which one we remove, the other three will have diameter sqrt(2) and second diameter 1.
```
{0, 0, 1, 2, 2}
```
```
{0, 10, 5, 0, 10}
```
```
Returns: 500
```
For each of the five sets S[0] through S[4] here the second diameter is 10. Note that S[2] contains two pairs of points that are sqrt(104) apart, but that does not make the second diameter equal to the diameter.
```
{1, 2, 3, 4, 5}
```
```
{1, 3, 6, 10, 15}
```
```
Returns: 534
```
The return value is computed as 85 + 90 + 153 + 153 + 53.

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.