All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef is working with lines on a 2-D plane.
He knows that every line on a plane can be clearly defined by three coefficients A, B and C: any point (x, y) lies on the line if and only if A * x + B * y + C = 0.
Let's call a set of lines to be perfect if there does not exist a point that belongs to two or more distinct lines of the set.
He has a set of lines on a plane and he wants to find out the size of the largest perfect subset of this set.
The first line of input contains one integers T denoting the number of test cases.
Each test case consists of one integer N denoting number of lines.
Next N lines contain 3 space-separated integers each denoting coefficients A, B and C respectively.
For each test case output the cardinality of the largest perfect subset in a single line.
- 1 ≤ N ≤ Nmax
- Sum over all N for all test cases ≤ NSmax
- |A|, |B|, |C| ≤ 109
- For a line with coefficients A, B and C either A or B is not zero.
- Subtask #1 [35 points]: Nmax = 5000, NSmax = 50000
- Subtask #2 [65 points]: Nmax = NSmax = 105
Input: 1 5 1 0 0 1 2 3 3 4 5 30 40 0 30 40 50 Output: 2
Lines 3*x + 4*y + 5 = 0 and 30*x + 40*y + 0 = 0 form a biggest perfect subset.
|Tags||cenadar, dec15, euclidean, gcd, parallel, sets, simple, sorting|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, 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, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.