Given N points on the plane, represented as (xi, yi) where both xi and yi are integers, you need to tell us the maximum number of distinct points that lie on a straight line.
Your algorithm needs to be really efficient.
The first line of the input contains the number of test cases T, atmost 10. Each of the next T lines contains the description of a single test case. Each test case begins with the value of N, the number of points in the plane, at most 700. Each of the next N lines contains two space separated integers which specify the coordinates of the points in the plane. Each point (xi, yi) satisfies -1000 <= xi, yi <= 1000.
For each test case in the input, print on a new line the maximum number of points that lie on a straight line.
Input: 1 5 1 0 2 1 3 2 4 4 -8 -8 Output: 3
|Time Limit:||0.206897 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, CS2, PAS fpc, PAS gpc, RUBY, PHP, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, SQL, TEXT|
Fetching successful submissions