OnePointNineNine | Topcoder Archive

Problem Statement

Jeip drew N black points onto the plane. The points were in a special configuration: for each pair of points, their distance was either at most D, or at least 1.99*D.

You are given the coordinates of the points as int[]s x and y. You are also given the int D.

Ouju wants to paint some (possibly none or all) of the N points red. The distance between any two red points must be at least 1.99*D. Return the number of ways to do this, modulo 1,000,000,007.

Definition

Class:: OnePointNineNine
Method:: countSubsets
Parameters:: int[], int[], int
Returns:: int
Method signature:: int countSubsets(int[] x, int[] y, int D)
(be sure your method is public)

Constraints

x and y will contain between 1 and 1000 elements, inclusive.
x and y will contain the same number of elements.
Each element of x and y will be between 0 and 1,000,000,000, inclusive.
D will be between 1 and 1,000,000,000, inclusive.
No two points are exactly at the same position.
The points are in a special configuration described in the statement.

Examples

```
{0,0,10,10}
```
```
{0,10,0,10}
```
```
47
```
```
Returns: 5
```
At most one of these four points can be red.
```
{0,0,10,10}
```
```
{0,10,0,10}
```
```
4
```
```
Returns: 16
```
Any subset of these four points can be red.
```
{0,4,8}
```
```
{0,3,6}
```
```
5
```
```
Returns: 5
```
In one of the valid solutions the points (0,0) and (8,6) are both red.

{0, 4, 8, 20, 25, 30, 35, 40}

{0, 3, 6, 20, 20, 20, 20, 20}

Returns: 65

{4637, 7770, 9911, 3887, 310, 8546, 104, 9820, 6710, 4128, 8224, 2492, 8956, 6162, 3392, 9736, 1540, 7744, 3783, 5451, 3756, 6153, 4846, 9852,
2678, 6500, 4117, 3994, 9126, 8950, 4913, 8598, 5692, 3400, 133, 4284, 656, 4742, 8727, 4904, 338, 7144, 7447, 8807, 1985, 6591, 40, 9614, 1839,
2724, 391, 1419, 2404, 9268, 1490, 3121, 654, 1337, 7787, 9269, 9413, 4515, 7787, 8622, 6718, 839, 238, 2490, 253, 1029, 9286, 5226, 180, 6451,
7826, 1707, 5119, 7238, 3393, 8980, 7234, 879, 5481, 703, 3991, 35, 3205, 2697, 9462, 4489, 2074, 7880, 1909, 150, 2378, 1555, 5232, 5959, 8755, 7679}

{4026, 2791, 3044, 4049, 6759, 6606, 3440, 8858, 6954, 2544, 4778, 2367, 5113, 8588, 3772, 4741, 3693, 5140, 8822, 8853, 9934, 6277, 5097, 285,
1031, 9872, 1012, 5883, 8992, 7257, 8889, 6558, 9997, 3868, 7731, 7508, 3729, 6398, 4102, 2054, 4835, 5707, 4271, 1676, 9487, 6336, 9829, 1058,
9965, 4998, 1042, 6320, 7669, 1893, 6021, 4211, 8496, 7585, 6882, 8410, 5155, 5869, 3376, 7173, 5726, 1574, 8911, 4192, 8324, 963, 8867, 7292,
7127, 4238, 6796, 6225, 4143, 7775, 4312, 965, 5933, 558, 8642, 268, 7208, 5688, 267, 4338, 4023, 7982, 4535, 545, 7228, 1884, 1660, 3241, 6388, 6572,
6515, 5912}

Returns: 976371285

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.