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) | |
| | {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. |
|
|
| 1) | |
| | {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. |
|
|
| 2) | |
| | {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. |
|
|
| 3) | |
| | {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. |
|
|
| 4) | |
| | {1, 2, 0, 3, 1} | {0, 3, 2, 1, 0} | {1, 1, 1} |
| Returns: 4 | |
|
| 5) | |
| | {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 | |
|