JOIN
Get Time

   Problem Statement  

 Problem Statement for OnePointNineNine

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,0,10,10}
{0,10,0,10}
47
Returns: 5
At most one of these four points can be red.
1)
    
{0,0,10,10}
{0,10,0,10}
4
Returns: 16
Any subset of these four points can be red.
2)
    
{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.
3)
    
{0, 4, 8, 20, 25, 30, 35, 40}
{0, 3, 6, 20, 20, 20, 20, 20}
5
Returns: 65
4)
    
{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}
1
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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       2014 TCO Algorithm Round 3B - Division I, Level Two
       2014 TCO Algorithm Parallel Round 3B - Division I, Level Two