Max Points on a Straight Line

You are given a set of n points in the 2D plane. Your task is to determine the maximum number of points that lie on a single straight line.

Formally, given points \( (x_i, y_i) \) for \( i = 1, 2, \ldots, n\), find the maximum count of points that can be aligned on one line. Two points \( (x_1, y_1) \) and \( (x_2, y_2) \) determine a line with a slope defined (when \( x_1 \neq x_2 \)) as:

[ \text{slope} = \frac{y_2 - y_1}{x_2 - x_1} ]

Vertical lines, where \( x_1 = x_2 \), should be handled as a special case. Points that are exactly the same are counted as overlapping.

Your program should read the input from standard input (stdin) and output the answer to standard output (stdout).

inputFormat

The first line contains a single integer n representing the number of points. Each of the next n lines contains two space-separated integers, x and y, representing the coordinates of a point.

Constraints: It is guaranteed that n ≥ 1 and the absolute value of the coordinates does not exceed 10⁴.

outputFormat

Output a single integer representing the maximum number of points that lie on a straight line.

6
1 1
2 2
3 3
4 4
5 5
1 2

5