MinimumSquare | Topcoder Archive

Problem Statement

There are N points in the plane. You are given their description as two int[]s, x and y, with N elements each. The N points have coordinates (x[0],y[0]), (x[1],y[1]), ..., (x[N-1],y[N-1]).

You want to draw a single square onto the plane. The vertices of the square must have integer coordinates, and the sides of the square must be parallel to the coordinate axes. There is one additional constraint: at least K of the N given points must lie strictly inside the square (i.e., not on its boundary).

You are given x, y, and the int K. Return the smallest possible area of a square that satisfies the constraints above.

Definition

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

Constraints

x will contain between 2 and 100 elements, inclusive.
y will contain the same number of elements as x.
K will be between 1 and the number of elements in x, inclusive.
All points will be pairwise distinct.
Each element of x will be between -1,000,000,000 and 1,000,000,000, inclusive.
Each element of y will be between -1,000,000,000 and 1,000,000,000, inclusive.

Examples

```
{0, 3}
```
```
{0, 7}
```
```
2
```
```
Returns: 81
```
The square we seek must contain both given points. One optimal solution is the square with opposite corners at (-1,-1) and (8,8).
```
{-4, 3, 1}
```
```
{3 , -1, -2}
```
```
2
```
```
Returns: 16
```

{0, 0, 1, 1, 2, 2}

{0, 1, 0, 1, 0, 1}

Returns: 9

{1000000000, 1000000000, 1000000000, -1000000000, -1000000000, -1000000000}

{1000000000, 0, -1000000000, 1000000000, 0, -1000000000}

Returns: 4000000008000000004

In this case one of the optimal solutions is a square that contains all six points.

{-47881, 28623, 1769, -38328, -16737, 16653, -23181, 37360, 41429, 26282, 254, 728, 8299, -41080, -29498, 17488, -23937, -11, 33319, 25232}

{-46462, 48985, -43820, -19587, -33593, -28337, 13667, -48131, -5568, -2332, -41918, -31370, -3695, 42599, -37788, -40096, 39049, 25045, -2122, 3874}

Returns: 1695545329

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.