Parallel Lines

Time limit10sMemory limit512 MB

Summary

Given up to 16 distinct points, pair them up to maximize the number of parallel pairs among the drawn segments.

Level: Hard8 of 10
Topics: Bit manipulation, Dynamic programming, Geometry, Combinatorics
Solved: No attempts yet

Problem

You are given an even number of distinct points on the plane. Couple all of the points into pairs so that every point is coupled with exactly one other point, and consider every such coupling.

Draw the segment that connects the two points of each couple. Some of the drawn segments are parallel to others. Find the maximum number of parallel segment pairs over all possible couplings.

For the four points $(0, 0)$ , $(1, 1)$ , $(0, 2)$ and $(2, 4)$ there are three couplings, shown in Figure B.1. The numbers of parallel segment pairs are 0, 0 and 1, from the left, so the maximum is 1.

Figure B.1. All three possible couplings of the four points

Eight points can be coupled as shown in Figure B.2. With that coupling all four segments are parallel to one another, so the six pairs $(L_1, L_2)$ , $(L_1, L_3)$ , $(L_1, L_4)$ , $(L_2, L_3)$ , $(L_2, L_4)$ and $(L_3, L_4)$ are parallel and the maximum is 6.

Figure B.2. A coupling of eight points that maximizes the number of parallel segment pairs

Input

The input consists of a single test case of the following format.

m
x1 y1
.
.
.
xm ym

The first line contains an even integer $m$ , the number of points ( $2 \le m \le 16$ ). Each of the following $m$ lines gives the coordinates of one point. The integers $x_i$ and $y_i$ in the $i$ -th of those lines are the x-coordinate and the y-coordinate of the $i$ -th point ( $-1000 \le x_i \le 1000$ , $-1000 \le y_i \le 1000$ ).

All points are at different positions, that is, $x_i \ne x_j$ or $y_i \ne y_j$ holds for all $i \ne j$ . No three points lie on a single line.

Output

Print the maximum number of parallel segment pairs in one line.

Examples5

Example 1
Input
```
4
0 0
1 1
0 2
2 4
```
Expected output
```
1
```
Example 2
Input
```
8
0 0
0 5
2 2
2 7
3 -2
5 0
4 -2
8 2
```
Expected output
```
6
```
Example 3
Input
```
6
0 0
0 5
3 -2
3 5
5 0
5 7
```
Expected output
```
3
```
Example 4
Input
```
2
-1000 1000
1000 -1000
```
Expected output
```
0
```

Example 5

Input

Expected output