MaximizeSquares | Topcoder Archive

Problem Statement

Consider an arrangement of N points on the cartesian plane. The "square count" of the points is the total number of distinct squares with sides parallel to the coordinate axes which can be built using 4 different points as vertices. Your task is to return the maximum square count, considering all possible arrangements of N points on the plane.

Definition

Class:: MaximizeSquares
Method:: squareCount
Parameters:: int
Returns:: int
Method signature:: int squareCount(int N)
(be sure your method is public)

Notes

Two squares are distinct if at least one of their corners is in a different location.

Constraints

N will be between 0 and 1000000, inclusive.

Examples

```
4
```
```
Returns: 1
```
Clearly, we can only make one square out of 4 points.
```
5
```
```
Returns: 1
```
No matter where we place a fifth point, we can't get any extra squares.
```
6
```
```
Returns: 2
```
We can get 2 squares by placing the points in the shape of a rectangle.
```
16
```
```
Returns: 14
```
```
115
```
```
Returns: 340
```

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.