Symmetry

Time limit5sMemory limit512 MB

Summary

Given up to 1000 distinct lattice points, find the minimum number of extra points needed to make the set symmetric about some point or some line.

Level: Hard8 of 10
Topics: Geometry, Hash map, Brute force, Math
Solved: No attempts yet

Problem

You are bored with nothing to do, so you stare at a pattern of spots on the wall in front of you. The pattern has no obvious symmetry. That grates on you more and more, and you start thinking about adding spots until the pattern is balanced. Solve this with a program.

You are given spots whose coordinates are between $-20000$ and $20000$ . Find the smallest number of extra spots needed to make the whole pattern symmetric. The symmetry is either about a point or about a line. If it is about a point, the center does not have to be one of the given spots, and its coordinates do not have to be integers. If it is about a line, the line may have any slope. The coordinates of the added spots may fall outside $-20000$ to $20000$ .

Input

The first line contains one integer $n$ ( $1 \le n \le 1000$ ), the number of spots.

Each of the next $n$ lines contains two space separated integers $x$ and $y$ ( $-20000 \le x, y \le 20000$ ), the coordinates of one spot. All spots are at distinct positions.

Output

Print one integer on a single line, the smallest number of spots that must be added so that all spots are symmetric about some point or about some line.

Examples2

Example 1
Input
```
4
0 0
1000 0
0 1000
1000 1000
```
Expected output
```
0
```

Example 2

Input

Expected output