PROBLEM STATEMENT
There are N points in the plane. You are given their description as two vector 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:vector , vector , int
Returns:long long
Method signature:long long minArea(vector x, vector y, int K)
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)
{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).
1)
{-4, 3, 1}
{3 , -1, -2}
2
Returns: 16
2)
{0, 0, 1, 1, 2, 2}
{0, 1, 0, 1, 0, 1}
4
Returns: 9
3)
{1000000000, 1000000000, 1000000000, -1000000000, -1000000000, -1000000000}
{1000000000, 0, -1000000000, 1000000000, 0, -1000000000}
3
Returns: 4000000008000000004
In this case one of the optimal solutions is a square that contains all six points.
4)
{-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}
8
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)2010, TopCoder, Inc. All rights reserved.