Symmetry

Interview

Time limit1sMemory limit128 MB

Summary

Given N distinct points in the plane, count how many lines reflect the whole set onto itself.

Level: Medium6 of 10
Topics: Geometry, Hash map, Sorting, Implementation
Solved: No attempts yet

Problem

Farmer John has plotted the locations of his $N$ cows ( $2 \le N \le 1000$ ) on the 2D plane, each cow occupying a distinct point. He wonders how many distinct lines of symmetry this set of points has.

A line of symmetry is a line such that reflecting every point across it yields exactly the same set of points; in other words, the points on the two sides of the line are mirror images of each other.

Count the number of lines of symmetry of the point set.

Input

Line $1$ : the single integer $N$ .
Lines $2 \dots N+1$ : line $i+1$ contains two space-separated integers, the $x$ and $y$ coordinates of the $i$ -th cow ( $-10000 \le x, y \le 10000$ ).

Output

Line $1$ : the number of distinct lines of symmetry of the point set.

Notes

For example, four points forming the corners of a square have $4$ lines of symmetry: one vertical, one horizontal, and two diagonal.

Examples3

Example 1
Input
```
4
0 0
0 1
1 0
1 1
```
Expected output
```
4
```
Example 2
Input
```
2
0 0
2 0
```
Expected output
```
2
```
Example 3
Input
```
3
0 0
4 0
2 3
```
Expected output
```
1
```