SquaredSubsets | Topcoder Archive

Problem Statement

Given a set of points in the XY plane and an integer n, a subset P of those points is called n-squared if it is not empty and there exists a square of side n in the XY plane with its sides parallel to the axes such that a point from the given set of points is in P if and only if it is contained within the square. A point lying on a side or a vertex of the square is considered to be contained in it.

You will be given n as explained in the input. You will also be given two int[]s x and y such that the coordinates of point i are (x[i],y[i]). Return the number of n-squared subsets in the input set described by x and y.

Definition

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

Constraints

n will be between 1 and 100000000 (10^8), inclusive.
x and y will contain between 1 and 50 elements, inclusive.
x and y will contain the same number of elements.
Each element of x and y will be between -100000000 (-10^8) and 100000000 (10^8), inclusive.
All described points will be different.

Examples

```
5
```
```
{-5,0,5}
```
```
{0,0,0}
```
```
Returns: 5
```
The following subsets are squared: {(-5,0)}, {(0,0)}, {(5,0)}, {(-5,0),(0,0)}, {(0,0),(5,0)}.
```
10
```
```
{-5,0,5}
```
```
{0,0,0}
```
```
Returns: 5
```
The following subsets are squared: {(-5,0)}, {(5,0)}, {(0,0),(5,0)}, {(-5,0),(0,0)}, {(-5,0),(0,0),(5,0)}.

100000000

{-1,-1,-1,0,1,1,1}

{-1,0,1,1,-1,0,1}

Returns: 21

{5,3,6,2,1,6,4,4,7,-1,-4,-7,2,-2,0}

{0,-1,8,-5,2,5,-8,8,-6,4,3,2,7,3,5}

Returns: 66

```
1
```
```
{-1,0}
```
```
{0,0}
```
```
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.