BestCircle | Topcoder Archive

Problem Statement

Given a set of points on a plane with x/y integer coordinates between -100 and 100 inclusive and an integer radius, determine the maximum number of these points a circle with the given radius can cover. (For the purposes of this problem, a circle covers a point if and only if the point is inside or exactly on the border of the circle).

Definition

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

Notes

The center of the circle need NOT be at a point with integer coordinates.
xCoor and yCoor are lists of x coordinates and y coordinates of the given points in the same order.

Constraints

xCoor contains between 1 and 50 elements inclusive
yCoor contains the same number of elements as xCoor
each element of xCoor and yCoor is between -100 and 100 inclusive
radius is between 1 and 150 inclusive

Examples

```
{1,1,5,5}
```
```
{1,5,1,5}
```
```
2
```
```
Returns: 2
```
These points are the vertices of a square. The best possible place for the center of a circle with radius 2 is in the middle of an edge.
```
{1,1,4,4}
```
```
{1,4,1,4}
```
```
3
```
```
Returns: 4
```
These points are the vertices of a square. The best possible place for the center of a circle with radius 3 is in the center of the square.

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

{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,
23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,
43,44,45,46,47,48,49,50}

Returns: 49

```
{1,1,1,3,3}
```
```
{1,3,5,1,5}
```
```
2
```
```
Returns: 3
```
```
{-100,1,100}
```
```
{-100,1,100}
```
```
150
```
```
Returns: 3
```

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.