Celtic Symmetry

Interview

Time limit2sMemory limit512 MB

Summary

Given up to 1000 distinct integer points in the plane, count the distinct lines of symmetry of the set.

Level: Medium7 of 10
Topics: Geometry, Hash map, Sorting, Math
Solved: No attempts yet

Problem

After a class on ancient Irish history, Diarmuid took an interest in geometric patterns hidden in the locations of neolithic tombs around Ireland. He plots the positions of $N$ tombs on the plane, and no two tombs sit at the same point. Count the lines of symmetry of this set of points.

A line of symmetry is a line such that the points on one side are mirror images of the points on the other side. In other words, reflecting every point of the set across the line must give back exactly the same set.

Input

The first line contains the number of tombs $N$ ( $2 \le N \le 1000$ ).

Each of the next $N$ lines contains two integers $x$ and $y$ , the coordinates of one tomb, separated by a space ( $-10000 \le x, y \le 10000$ ). No coordinate pair is given twice.

Output

Print the number of distinct lines of symmetry of the point set.

Examples2

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