Game of Lines

Interview

Time limit1sMemory limit128 MB

Summary

Given N distinct lattice points, count how many distinct slopes the lines through pairs of points can have.

Level: Easy3 of 10
Topics: Hash map, Math, Geometry, Implementation
Solved: No attempts yet

Problem

Farmer John has challenged Bessie to the following game. FJ has a board with $N$ ( $2 \le N \le 200$ ) distinct lattice points marked on it. Point $i$ has the integer coordinates $X_i$ and $Y_i$ ( $-1000 \le X_i, Y_i \le 1000$ ).

Bessie scores a point by choosing two of the marked points and drawing the straight line through them. However, she may not draw a line if she has already drawn another line parallel to it. Two lines are parallel when they have the same slope, and two vertical lines are also considered parallel to each other.

Help Bessie find the maximum number of lines she can draw such that no two of them are parallel. In other words, count the number of distinct slopes among all pairs of points.

Input

Line 1: A single integer $N$ .
Lines 2.. $N+1$ : Line $i+1$ contains two space-separated integers $X_i$ and $Y_i$ , the coordinates of point $i$ .

Output

A single integer: the maximum number of lines Bessie can draw, no two of which are parallel.

Hint

In the example, Bessie can draw lines of the four slopes -1, 0, 1/3, and 1.

Examples4

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