ColorfulEnclosure | Topcoder Archive

Problem Statement

Note: This problem has a nonstandard time limit: 4 seconds.

We have n points in the plane. The points are numbered 0 through n-1. You are given the coordinates of these points in the int[]s x and y. More precisely, for each valid i, point i has coordinates (x[i], y[i]). Multiple points may share the same coordinates.

Each point has one of k distinct colors. The colors are numbered 0 through k-1. You are given the int k. You are also given the int[] c, where c[i] is the color of point i. It is guaranteed that each of the k colors appears in c at least once.

We want to find a rectangle with the following properties:

The sides of the rectangle must be parallel to the coordinate axes.
The rectangle must contain (inside or on its boundary) at least one point of each of the k colors.
The area of the rectangle must be as small as possible.

Note that the rectangle is allowed to be degenerate: one or both of its sides may have length equal to zero.
Compute and return the smallest possible area of such a rectangle.

Definition

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

Constraints

n will be between 1 and 1,500, inclusive.
k will be between 1 and n, inclusive.
x, y and c will contain exactly n elements.
Each element in x and y will be between -1,000,000,000 and 1,000,000,000, inclusive.
Each element in c will be between 0 and k-1, inclusive.
c will contain all k colors.

Examples

```
2
```
```
{0,1,2,3}
```
```
{0,2,1,3}
```
```
{0,1,1,0}
```
```
Returns: 2
```
There are four points: the points at (0,0) and (3,3) have color 0 and the points at (1,2) and (2,1) have color 1. There are multiple optimal solutions. One of them is to choose the rectangle with two opposite corners at (1,2) and (3,3).
```
3
```
```
{3,2,1}
```
```
{1,1,1}
```
```
{0,1,2}
```
```
Returns: 0
```
This is an example of a test case where the optimal rectangle is degenerate. For example, one optimal solution is to choose the rectangle with opposite corners at (-4,1) and (7,1).

{-1000000,-1000000,1000000,1000000}

{1000000,1000000,-1000000,-1000000}

{0,1,2,3}

Returns: 4000000000000

Several points can share the same coordinates.

{0,9,8,2,0,9,4,2}

{7,0,9,3,9,3,2,2}

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

Returns: 9

{37,80,52,30,33,89,62,84,80,70,15,13,34,28,14,70,99,77,91,74}

{29,88,45,67,50,78,71,17,32,22,53,46,92,37,77,42,78,70,15,35}

{2,1,0,1,4,3,3,1,4,1,2,0,4,2,4,0,1,3,1,2}

Returns: 480

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.