#K49227. Valid Radii Count

    ID: 28596 Type: Default 1000ms 256MiB

Valid Radii Count

Valid Radii Count

You are given n points in the 2D plane with integer coordinates. For each point, consider the squared radius of a circle centered at that point that just reaches the farthest of the other points. In other words, for each point p, let

\( d(p)=\max_{q\neq p}\left((p_x - q_x)^2+(p_y - q_y)^2\right) \)

Your task is to count the number of distinct values among all d(p). Note that if there is only one point, it is considered to have a valid radius (output 1).

inputFormat

The input is read from stdin and is structured as follows:

  • The first line contains a single integer n (1 ≤ n ≤ 105), the number of points.
  • The next n lines each contain two integers x and y (−109 ≤ x, y ≤ 109), representing the coordinates of a point.

outputFormat

Print a single integer to stdout representing the number of distinct squared radii (as defined above) among all points.

## sample
4
1 1
2 2
3 3
4 4
2

</p>