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.

------ Input ------ 

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.

------ Output ------ 

For each test case output the cardinality of the largest perfect subset in a single line.

------ Constraints ------ 

$1 ≤ N ≤ N_{max}$
$Sum over all N for all test cases ≤ NS_{max}$
$|A|, |B|, |C| ≤ 10^{9}$
$For a line with coefficients A, B and C either A or B is not zero.$

------ Subtasks ------ 

$Subtask #1 [35 points]: N_{max} = 5000, NS_{max} = 50000$
$Subtask #2 [65 points]: N_{max} = NS_{max} = 10^{5}$

----- Sample Input 1 ------ 
1
5
1 0 0
1 2 3
3 4 5
30 40 0
30 40 50
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
Lines 3*x + 4*y + 5 = 0 and 30*x + 40*y + 0 = 0 form a biggest perfect subset.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Geometry

Number theory

Mathematics


Solutions:
from collections import defaultdict
for _ in range(int(input())):
	N = int(input())
	z = defaultdict(lambda : 0)
	y = defaultdict(lambda : 0)
	undefined = defaultdict(lambda : 0)
	undv = 0
	for i in range(N):
		(A, B, C) = list(map(int, input().split()))
		if B != 0:
			m = -A / B
			b = -C / B
			if (m, b) not in y:
				y[m, b] = 1
				z[m] += 1
		elif A != 0:
			m = -C / A
			if m not in undefined:
				undefined[m] = 1
				undv += 1
	if len(z) > 0:
		print(max(max(z.values()), undv))
	else:
		print(max(1, undv))


for z in range(int(input())):
	n = int(input())
	a = {}
	for i in range(n):
		b = [int(x) for x in input().split()]
		if b[0] == 0:
			m = 'a'
			q = b[2] / b[1]
		else:
			m = b[1] / b[0]
			q = b[2] / b[0]
		if m in a:
			a[m].append(q)
		else:
			a[m] = [q]
	m = 0
	for x in a.keys():
		m = max(m, len(set(a[x])))
	print(m)


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
from collections import defaultdict
for _ in range(int(input())):
	s = defaultdict(set)
	for i in range(int(input())):
		(a, b, c) = map(int, input().split())
		g = gcd(a, b)
		h = gcd(g, c)
		s[a / g, b / g].add((a / h, b / h, c / h))
	print(max(map(len, s.values())))


import math
T = int(input())
for i in range(T):
	N = int(input())
	dicto = {}
	dicto2 = {}
	for j in range(N):
		temp = str(input()).split(' ')
		temp1 = int(temp[0])
		temp2 = int(temp[1])
		temp3 = int(temp[2])
		b = math.gcd(math.gcd(temp1, temp2), temp3)
		temp1 = temp1 // b
		temp2 = temp2 // b
		temp3 = temp3 // b
		if temp1 < 0:
			temp1 = -temp1
			temp2 = -temp2
			temp3 = -temp3
		elif temp1 == 0 and temp2 < 0:
			temp2 = -temp2
			temp3 = -temp3
		flag = dicto2.get((temp1, temp2, temp3), False)
		if not flag:
			dicto2[temp1, temp2, temp3] = True
			a = math.gcd(temp1, temp2)
			temp1 = temp1 // a
			temp2 = temp2 // a
			dicto[temp1, temp2] = dicto.get((temp1, temp2), 0) + 1
	maxim = 0
	for (k, v) in dicto.items():
		if v > maxim:
			maxim = v
	print(maxim)


from collections import defaultdict
from fractions import gcd
T = int(input())
for i in range(T):
	x = int(input())
	lines = defaultdict(set)
	for i in range(x):
		(a, b, c) = map(int, input().split())
		g = gcd(a, b)
		h = gcd(g, c)
		lines[a / g, b / g].add((a / h, b / h, c / h))
	print(max(map(len, lines.values())))


from collections import defaultdict
from fractions import gcd

def res():
	for _ in range(int(input())):
		n = int(input())
		s = defaultdict(set)
		for i in range(n):
			(a, b, c) = map(int, input().split())
			g = gcd(a, b)
			h = gcd(g, c)
			s[a / g, b / g].add((a / h, b / h, c / h))
		print(max(map(len, s.values())))
res()


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input())
for _ in range(t):
	n1 = int(input())
	arr = []
	for __ in range(n1):
		(a, b, c) = list(map(int, input().split()))
		z = gcd(a, b)
		h = gcd(z, c)
		try:
			(a, b, c) = (a / h, b / h, c / h)
			m = b / a
			arr.append((a, b, c, m))
		except:
			arr.append((a, b, c, 'ver'))
	arr = list(set(arr))
	dic = dict()
	for x in arr:
		(a, b, c, m) = x
		try:
			dic[m] += 1
		except:
			dic[m] = 1
	print(max(dic.values()))


from collections import defaultdict
for _ in range(int(input())):
	slopes = defaultdict(set)
	for _ in range(int(input())):
		(a, b, c) = map(int, input().split())
		if b == 0:
			slopes['vertical'].add(c / a)
		else:
			slopes[a / b].add(c / b)
	result = 1
	for x in slopes:
		result = max(len(slopes[x]), result)
	print(result)


for _ in range(int(input())):
	numlines = int(input())
	slopes = {}
	vert_slopes = set()
	for _ in range(numlines):
		(a, b, c) = map(int, input().split())
		if b == 0:
			vert_slopes.add(c / a)
		else:
			if a / b not in slopes:
				slopes[a / b] = set()
			slopes[a / b].add(c / b)
	result = 1
	for x in slopes:
		if len(slopes[x]) > result:
			result = len(slopes[x])
	print(max(result, len(vert_slopes)))


def run():
	T = int(input())
	for t in range(T):
		N = int(input())
		lines = []
		while N > 0:
			N -= 1
			(A, B, C) = map(int, input().split())
			if B == 0:
				m = float('inf')
				c = C / A
			else:
				m = A / B
				c = C / B
			lines.append((m, c))
		lines.sort()
		max_len = 1
		cur_len = 1
		for i in range(0, len(lines) - 1):
			first = lines[i]
			second = lines[i + 1]
			if first[0] == second[0] and first[1] != second[1]:
				cur_len += 1
			elif first == second:
				continue
			else:
				cur_len = 1
			max_len = max(cur_len, max_len)
		print(max_len)
run()


from sys import stdin
from fractions import gcd
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	d = {}
	for _ in range(n):
		(a, b, c) = map(int, stdin.readline().split())
		h = gcd(a, b)
		g = gcd(h, c)
		if (a // h, b // h) not in d:
			d[a // h, b // h] = set()
		d[a // h, b // h].add((a // g, b // g, c // g))
	print(max(map(len, d.values())))


from fractions import gcd
from collections import defaultdict
t = int(input())
for _ in range(0, t):
	s = defaultdict(set)
	for i in range(int(input())):
		(a, b, c) = map(int, input().split())
		g = gcd(a, b)
		h = gcd(g, c)
		s[a / g, b / g].add((a / h, b / h, c / h))
	count = 0
	print(max(map(len, s.values())))


t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	d = {}
	ans = 1
	for j in range(n):
		(a, b, c) = map(float, input().strip().split()[:3])
		if b != 0:
			(x, y) = (a / b, c / b)
		else:
			(x, y) = (10 ** 10, c / a)
		if x in d:
			if not y in d[x]:
				d[x][y] = 1
				ans = max(ans, len(d[x]))
		else:
			d[x] = {}
			d[x][y] = 1
	print(ans)


def main():
	t = int(input())
	for tt in range(t):
		N = int(input())
		d = {}
		x = set()
		y = set()
		for NN in range(N):
			a = [int(i) for i in input().split(' ')]
			if a[0] == 0:
				y.add(a[2] / a[1])
			elif a[1] == 0:
				x.add(a[2] / a[0])
			elif a[0] / a[1] in d:
				d[a[0] / a[1]].add(a[2] / a[1])
			else:
				d[a[0] / a[1]] = set([a[2] / a[1]])
		if len(d):
			print(max([len(x), len(y), max((len(d[j]) for j in d))]))
		else:
			print(max(len(x), len(y)))
main()


test = float('inf')
t = int(input())
(one, two, three) = (0, 0, 0)
for test_case in range(t):
	n = int(input())
	myset = set()
	for rn in range(n):
		line = input()
		line = list(map(int, line.split()))
		A = line[0]
		B = line[1]
		C = line[2]
		if B == 0:
			one = test
			two = test
			three = C / A
		else:
			one = A / B
			two = C / B
		if A == 0:
			three = test
		else:
			three = C / A
		t = (one, two, three)
		myset.add(t)
	maxc = 0
	count = 1
	mylist = []
	for (one, two, three) in myset:
		mylist.append(one)
	mylist.sort()
	for i in range(1, len(mylist)):
		if mylist[i] == mylist[i - 1]:
			count = count + 1
		else:
			maxc = max(maxc, count)
			count = 1
	maxc = max(count, maxc)
	print(maxc)


from fractions import Fraction
from collections import defaultdict
t = int(input())
for x in range(0, t):
	n = int(input())
	lines = defaultdict(set)
	vertical = set()
	for i in range(0, n):
		l = list(map(int, input().split()))
		if l[1] is not 0:
			lines[Fraction(l[0], l[1])].add(Fraction(l[2], l[1]))
		else:
			vertical.add(Fraction(l[2], l[0]))
	max = 0
	o = len(lines)
	v = len(vertical)
	for line in lines:
		length = len(lines[line])
		if max < length:
			max = length
	if max < v:
		max = v
	print(max)


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
t = int(input())
for i in range(1, t + 1):
	n = int(input())
	dict1 = {}
	max1 = 1
	for j in range(1, n + 1):
		(a, b, c) = list(map(int, input().split()))
		gcd1 = gcd(a, b)
		a = a // gcd1
		b = b // gcd1
		c = c / gcd1
		ls = str([a, b])
		if ls in dict1.keys():
			if c in dict1[ls][1].keys():
				continue
			else:
				temp = dict1[ls][0]
				temp += 1
				dict1[ls][0] = temp
				temp2 = dict1[ls][1]
				temp2[c] = True
				dict1[ls][1] = temp2
				if max1 < temp:
					max1 = temp
		else:
			dict1[ls] = [1, {c: True}]
	print(max1)


def mergeSort(alist):
	if len(alist) > 1:
		mid = len(alist) // 2
		lefthalf = alist[:mid]
		righthalf = alist[mid:]
		mergeSort(lefthalf)
		mergeSort(righthalf)
		i = 0
		j = 0
		k = 0
		while i < len(lefthalf) and j < len(righthalf):
			if lefthalf[i][0] == righthalf[j][0]:
				if lefthalf[i][1] < righthalf[j][1]:
					alist[k] = lefthalf[i]
					i = i + 1
				else:
					alist[k] = righthalf[j]
					j = j + 1
			elif lefthalf[i][0] < righthalf[j][0]:
				alist[k] = lefthalf[i]
				i = i + 1
			else:
				alist[k] = righthalf[j]
				j = j + 1
			k = k + 1
		while i < len(lefthalf):
			alist[k] = lefthalf[i]
			i = i + 1
			k = k + 1
		while j < len(righthalf):
			alist[k] = righthalf[j]
			j = j + 1
			k = k + 1
t = int(input())
while t != 0:
	n = int(input())
	alist = []
	m = 1
	for i in range(n):
		(a, b, c) = map(int, input().split())
		if b != 0:
			sl = -a / b
			cp = -c / b
		else:
			sl = 1000000001
			cp = -c / a
		q = []
		q.append(sl)
		q.append(cp)
		alist.append(q)
	mergeSort(alist)
	s = 1
	for i in range(n - 1):
		if alist[i][0] == alist[i + 1][0]:
			if alist[i][1] != alist[i + 1][1]:
				s += 1
		else:
			if m < s:
				m = s
			s = 1
	if m < s:
		m = s
	print(m)
	t -= 1


from fractions import *
for tests in range(int(input())):
	lines = {}
	for line in range(int(input())):
		(x, y, C) = [int(i) for i in input().split()]
		if y == 0:
			grad = 'inf'
			C = Fraction(C, x)
		else:
			grad = Fraction(x, y)
			C = Fraction(C, y)
		try:
			lines[grad].add(C)
		except:
			lines[grad] = set([C])
	best = 0
	for grad in lines:
		best = max(best, len(lines[grad]))
	print(best)


t = int(input())
for i in range(t):
	n = int(input())
	a = {}
	for x in range(n):
		(A, B, C) = map(int, input().split())
		if B == 0:
			temp = 9999.9879
			temp2 = C / A
		else:
			temp = A / B
			temp2 = C / B
		if temp not in a:
			a[temp] = {temp2: 0}
		elif temp2 not in a[temp]:
			a[temp][temp2] = 0
	print(len(max(a.values(), key=len)))


from sys import stdin
from collections import defaultdict

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def main():
	nextint = map(int, stdin.read().split()).__next__
	for _ in range(nextint()):
		n = nextint()
		lines = []
		for _ in range(n):
			(a, b, c) = (nextint(), nextint(), nextint())
			gcdabc = gcd(gcd(a, b), c)
			(a, b, c) = (a // gcdabc, b // gcdabc, c // gcdabc)
			lines.append((a, b, c))
		counter = defaultdict(set)
		for (a, b, c) in lines:
			gcdab = gcd(a, b)
			(a, b) = (a // gcdab, b // gcdab)
			if (-a, -b) in counter:
				counter[-a, -b].add(-c / float(gcdab))
			else:
				counter[a, b].add(c / float(gcdab))
		print(max([len(s) for s in counter.values()]))
main()


from collections import defaultdict
T = int(input())
for iii in range(T):
	cons = defaultdict(set)
	n = int(input())
	zeros = set()
	slopes = []
	for i in range(n):
		(a, b, c) = [int(x) for x in input().split()]
		if a == 0:
			zeros.add(c / b)
			continue
		b = b / a
		c = c / a
		if b not in cons.keys():
			cons[b] = set()
			cons[b].add(c)
			slopes.append(b)
		elif c not in cons[b]:
			cons[b].add(c)
			slopes.append(b)
	slopes = sorted(slopes)
	l = len(slopes)
	mm = 1
	i = 0
	while i < l - 1:
		m = 1
		while slopes[i + 1] == slopes[i]:
			m += 1
			i += 1
			if i == l - 1:
				break
		if m > mm:
			mm = m
		i += 1
	mm = max(mm, len(zeros))
	print(mm)


from collections import Counter
from fractions import Fraction, gcd
for _ in range(int(input())):
	n = int(input())
	s = set()
	for _ in range(n):
		(a, b, c) = map(int, input().split())
		g = gcd(a, b)
		s.add((a // g, b // g, Fraction(c, g)))
	ct = Counter(((a, b) for (a, b, c) in s))
	print(ct.most_common(1)[0][1])


import fractions
from collections import defaultdict
frac = fractions.Fraction
INF = 10000000000
t = int(input())
for x in range(0, t):
	sni = defaultdict(set)
	N = int(input())
	for y in range(0, N):
		(a, b, c) = map(int, input().split(' '))
		if b == 0:
			sni[frac(INF, 1)].add(frac(-c, a))
		else:
			sni[frac(-a, b)].add(frac(-c, b))
	maxCount = 0
	for y in sni:
		if len(sni[y]) > maxCount:
			maxCount = len(sni[y])
	print(maxCount)


from fractions import Fraction
from collections import defaultdict
for _ in range(0, int(input())):
	x = int(input())
	s = []
	t = []
	d = defaultdict(list)
	for i in range(0, x):
		(a, b, c) = map(int, input().split())
		if b != 0:
			s.append((-a / b, -c / b))
		else:
			t.append(-c / a)
	for (k, v) in set(s):
		d[k].append(v)
	maxcnt = 0
	for (k, v) in d.items():
		tempcnt = len(v)
		if maxcnt < tempcnt:
			maxcnt = tempcnt
	print(max(maxcnt, len(set(t))))


def F():
	return [int(x) for x in input().split()]
[T] = F()
while T:
	T -= 1
	N = int(input())
	d = {}
	while N:
		N -= 1
		[A, B, C] = F()
		if A == 0:
			slope = 'y'
			const = C / B
		else:
			slope = B / A
			const = C / A
		if slope in d:
			if const not in d[slope]:
				d[slope][const] = 1
		else:
			d[slope] = {const: 1}
	maxcount = 0
	for slope in d:
		l_const = len(d[slope])
		if l_const > maxcount:
			maxcount = l_const
	print(maxcount)


T = int(input())
while T > 0:
	N = int(input())
	d = {}
	while N > 0:
		[A, B, C] = [int(x) for x in input().split()]
		if B != 0:
			m = -A / B
			c = -C / B
		else:
			m = 'inf'
			c = -C / A
		if m not in d:
			d[m] = {}
			d[m][c] = 0
		elif c not in d[m]:
			d[m][c] = 0
		N -= 1
	max = 0
	for m in d:
		if len(d[m]) > max:
			max = len(d[m])
	print(max)
	T -= 1


from collections import Counter
a1 = int(input())
while a1 > 0:
	a1 -= 1
	b = int(input())
	A = []
	B = []
	for i in range(b):
		c1 = input()
		(a, b, c) = [int(n) for n in c1.split()]
		if a < 0:
			b = -b
			c = -c
			a = -a
		if b != 0:
			A.append((a / b, c / b))
		else:
			B.append(c / a)
	A = list(set(A))
	A.sort()
	s = 1
	v = Counter((i[0] for i in A))
	if len(v) > 0:
		s = v.most_common()[0][1]
	s1 = len(set(B))
	if s1 > s:
		s = s1
	print(s)


from fractions import gcd
for _ in range(int(input())):
	N = int(input())
	a = {}
	for i in range(N):
		(x, y, c) = map(int, input().split())
		m = gcd(x, y)
		x = round(x / m)
		y = round(y / m)
		c /= m
		if (x, y) not in a:
			a[x, y] = {c}
		else:
			a[x, y].add(c)
	print(max((len(a[i]) for i in a)))