SubgridsCounter | Topcoder Archive

Problem Statement

This problem contains images best viewed from the applet.

You are given several points on the plane. Nine points form a 3x3 subgrid if they are situated on the vertices of a 2x2 rectangle of equal size squares. The sides of the rectangle must be parallel to the coordinate axes.

The orange points form a subgrid among all the points on the picture.

You are given int[]s x and y, where (x[i], y[i]) are the coordinates of the i-th point on the plane. The points are distinct. Return the number of distinct subgrids you can create with these points. Two subgrids are distinct if one contains a point that is not contained in the other.

Definition

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

Constraints

x will contain between 1 and 50 elements, inclusive.
x and y will contain the same number of elements.
Each element of x will be between -1000 and 1000, inclusive.
Each element of y will be between -1000 and 1000, inclusive.
All points represented by (x[i], y[i]) will be distinct.

Examples

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

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

Returns: 4

This is a 4x4 regular grid.

```
{7,0,14,0,7,14,14,0,7}
```
```
{14,0,14,14,7,7,0,7,0}
```
```
Returns: 1
```
This is a 3x3 grid. It forms the only subgrid by itself.

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

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

Returns: 1

{6,0,4,0,20,0,0,4,12,6,6,12,12,6,0,12,4,6,4,4,20,20,20,6,6,4,20,4,20,12,12,0,12,0,20}

{4,10,10,9,10,25,0,16,25,0,18,0,4,10,4,16,4,16,25,18,9,4,18,9,25,0,0,9,25,9,18,16,10,18,16}

Returns: 1

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.