All submissions for this problem are available.
Once upon a time, there was a Kingdom of Seven Roads. Besides a fancy name, it actually had exactly 7 straight roads. Its residents wanted to keep track of the distances they traveled so they placed milestones along some roads. The roads slowly deteriorated and disappeared but some milestones remained. Archeologists documented remaining milestones and want to reconstruct the kingdom, starting with its main road. Help them by finding the maximum number of collinear milestones.
The first line contains a single integer T, the number of test cases. The first line of each testcase contains the number of documented milestones N. Following lines give the coordinates (Xi, Yi) of those milestones. Coordinates of all milestones will be different.
For each test case, output the maximum number of collinear milestones.
- T <= 30
- 1 <= N <= 10 000
- -15 000 <= Xi, Yi <= 15 000
Input: 2 5 0 0 1 0 2 0 1 1 3 1 2 1 1 10 10 Output: 3 2
|Tags||feb11, hard, thocevar|
|Time Limit:||0.858065 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.