Meteor | Topcoder Archive

Problem Statement

You are a sorceress trying to kill cows on the secret cow level. The level is represented as a square with x/y coordinates from 0 to 100. The cows are located at some points on this square with integer coordinates. The only spell available to you is Meteor. You can center Meteor at any point with integer coordinates and Meteor will half-kill all the cows within a given distance from its center.

Your task is, given the locations of the cows and the radius within which the Meteor produces damage, return the minimum number of times you need to fire the Meteor to kill all the cows.

Definition

Class:: Meteor
Method:: numHits
Parameters:: int[], int[], int
Returns:: int
Method signature:: int numHits(int[] xCoor, int[] yCoor, int radius)
(be sure your method is public)

Notes

xCoor represents x coordinates of the cows. yCoor represents y coordinates of the cows in the same order.
The cows on the border of the Meteor get damage. For example, if there is a cow at coordinates 1,1 and the Meteor is fired with the radius 1 at the point 1,2, the cow gets damage.
You need to hit each cow twice (not necessarily firing Meteor at the same point) to kill it.

Constraints

xCoor has between 1 and 18 elements inclusive
yCoor has the same number of elements as xCoor
each element of xCoor and yCoor is between 0 and 100 inclusive
radius is between 1 and 100 inclusive

Examples

{1,26,2,25,3,24,4,23,5,22,6,21,7,20,8,19,9,18}

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

Returns: 8

```
{0,0,2,2}
```
```
{0,2,0,2}
```
```
2
```
```
Returns: 2
```
if you fire the Meteor at coordinates 1,1 you will hit all the cows
```
{0,0,0,0}
```
```
{0,0,0,0}
```
```
3
```
```
Returns: 2
```
All cows are located at the same spot

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

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

Returns: 10

{89,86,50,50,21,31,98,44,2,55,39,76,15,42,18,1,91,69}

{64,75,33,20,93,37,49,100,62,40,60,1,93,52,3,47,20,94}

Returns: 11

This is probably not the worst case.

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.