ThreeWatchtowers | Topcoder Archive

Problem Statement

You wish to build three watchtowers to overlook several points of interest. The points of interest are given in the int[]s x and y, where each element of x and the corresponding element of y represent the coordinates of a single point of interest.

Each of the three watchtowers has a field of view that is the same in all directions. The viewing distance of each of the three watchtowers is given in the int[] view, so the i-th watchtower can see all points which are located not further than view[i] units from it. Assuming optimal placement, return the maximum number of points of interest that are within view of at least one of the watchtowers.

Definition

Class:: ThreeWatchtowers
Method:: maximumCoverage
Parameters:: int[], int[], int[]
Returns:: int
Method signature:: int maximumCoverage(int[] x, int[] y, int[] view)
(be sure your method is public)

Notes

Even though points of interest are restricted to a given area, the watchtowers themselves may be located outside of that area, and do not necessarily have to be placed on lattice points.
A watchtower can see a point exactly on the edge of its field of view. Thus, a watchtower at (0, 0) with a radius of 2 could see a point at (0, 2).

Constraints

x and y will each contain between 1 and 20 elements, inclusive.
x and y will each contain the same number of elements.
Each element of x and y will be between 0 and 20, inclusive.
view will contain exactly 3 elements.
Each element of view will be between 1 and 20, inclusive.

Examples

```
{0, 10, 20}
```
```
{15, 16, 20}
```
```
{1, 1, 1}
```
```
Returns: 3
```
Even though the watchtowers can't see very far, with only three points of interest, it is trivial to cover them all.
```
{0, 1, 10, 20, 15, 14}
```
```
{1, 0, 10, 20, 18, 12}
```
```
{2, 2, 2}
```
```
Returns: 4
```
The first two points are close enough together to be covered by a single watchtower. The other points are too spread out, so the other two towers can each only see a single point.
```
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
```
```
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
```
```
{1, 1, 13}
```
```
Returns: 10
```
The first two watchtowers are not really needed, since the last one has a wide enough range to see all 10 points at once.
```
{0, 5, 6, 16, 18, 20}
```
```
{0, 6, 7, 20, 20, 20}
```
```
{1, 3, 5}
```
```
Returns: 6
```
The first watchtower covers the first point. The second watchtower can cover the next two points. The last three points can be covered by the final tower.

{1, 2, 0, 3, 1}

{0, 3, 2, 1, 0}

{1, 1, 1}

Returns: 4

{10, 18, 16, 9, 17, 20, 4, 3, 11, 9}

{4, 17, 6, 14, 14, 14, 12, 12, 13, 16}

{1, 1, 2}

Returns: 7

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.