eolymp
bolt
Try our new interface for solving problems
Problems

Rabbit Hunt

Rabbit Hunt

A good hunter kills two rabbits with one shot. Of course, it can be easily done since for any two points we can always draw a line containing the both. But killing three or more rabbits in one shot is much more difficult task. To be the best hunter in the world one should be able to kill the maximal possible number of rabbits. Assume that rabbit is a point on the plane with integer \textbf{x} and \textbf{y} coordinates. Having a set of rabbits you are to find the largest number of rabbits that can be killed with single shot, i.e. maximum number of points lying exactly on the same line. No two rabbits sit at one point. \InputFile The first line contains the number of rabbits \textbf{n }(\textbf{3 }≤ \textbf{n }≤ \textbf{200}). Each of the next \textbf{n }lines contains \textbf{x }and \textbf{y }(-\textbf{2000 }≤ \textbf{x}, \textbf{y }≤ \textbf{2000}) coordinates (in this order) separated by a space. \OutputFile Print the maximal number of rabbits that are in one line.
Time limit 1 second
Memory limit 16 MiB
Input example #1
6
7 122
8 139
9 156
10 173
11 190
-100 1
Output example #1
5
Author Stanislav Vasilyev
Source Ural State University collegiate programming contest (25.03.2000)