Хороший охотник убивает двух зайцев одним выстрелом. Конечно же это может быть легко сделано, поскольку через любые две точки можно провести прямую. Но убить трёх и более зайцев одним выстрелом — намного более сложная задача. Чтобы стать лучшим охотником в мире, нужно уметь убить максимально возможное количество зайцев. Представим зайца точкой на плоскости. Точка задаётся целочисленными координатами x и y. Вам нужно найти максимальное число зайцев, которые могут быть убиты одним выстрелом, то есть максимальное количество точек заданного множества, лежащих точно на одной прямой. Никакие два зайца не находятся в одной точке.
Исходные данные
Первая строка ввода содержит целое число N (3 ≤ N ≤ 200) — количество зайцев. Каждая из следующих N строк содержит x и y координаты (в таком порядке), разделённые пробелом (−2000 ≤ x, y ≤ 2000).
Результат
Выведите максимальное число зайцев, находящихся на одной прямой.
Пример
исходные данные | результат |
---|
6
7 122
8 139
9 156
10 173
11 190
-100 1
| 5
|
Автор задачи: Станислав Васильев
Источник задачи: Ural State University collegiate programming contest (25.03.2000)