You are given an infinite two-dimensional grid. There are N balloons placed at certain coordinates of the grid. You have an arrow with yourself, which you will be using to shoot the balloons. You can select any point on the grid as your starting point and any point on the grid as the target point. When you fire the arrow, all ballons lying on the shortest path between the starting point and target point will be burst. Given the coordinates of the N ballons in an array arr, your task is to find out the maximum number of balloons that you can fire in one arrow shot.
Example 1:
Input:
N = 3
arr[] = {{1, 2}, {2, 3}, {3, 4}}
Output:
3
Explanation:
If you position yourself at point (1,2)
and fire the arrow aiming at the point (3,4).
Then all the balloons will burst.
Example 2:
Input: 
N = 3
arr[] = {{2,2}, {0,0}, {1,2}} 
Output:
2
Explanation: 
If you position yourself at point (2,2)
and fire the arrow aiming at the point (0,0).
Then the two balloons present at the two points
will burst.
Your Task:
Complete the function mostBalloons() which takes the integers N and the array arr as the input parameters, and returns the maximum number of balloons that can be burst using one arrow.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{3}
-10^{9} ≤ arr[i][j] ≤ 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Geometry

Mathematics

Starter code: #User function Template for python3



class Solution: 

    def mostBalloons(self, N, arr):

        # Code here

Solutions:
from math import gcd

class Solution:

	def mostBalloons(self, N, arr):
		if N < 3:
			return N
		ans = 0
		for i in range(N - 1):
			a = arr[i]
			di = {}
			curr = 1
			for j in range(i + 1, N):
				b = arr[j]
				rise = b[1] - a[1]
				run = b[0] - a[0]
				if rise == 0 and run == 0:
					curr += 1
				elif rise == 0 or run == 0:
					if rise:
						s = 10 ** 9 + 1
					else:
						s = 0
					di[s] = di.get(s, 0) + 1
				else:
					s = rise / run
					di[s] = di.get(s, 0) + 1
			for i in di.values():
				ans = max(ans, i + curr)
		return ans


class Solution:

	def mostBalloons(self, N, arr):
		arr.sort()
		m = {}
		ans = 0
		for i in range(N):
			cnt = 0
			for j in range(i + 1, N):
				if arr[j][1] == arr[i][1] and arr[j][0] == arr[i][0]:
					cnt += 1
				else:
					dy = arr[j][1] - arr[i][1]
					dx = arr[j][0] - arr[i][0]
					if dx == 0:
						slope = 100001
					else:
						slope = dy / dx
					m[slope] = 1 + m.get(slope, 0)
			for i in m.values():
				ans = max(ans, i + cnt)
			m = {}
		return ans + 1


from collections import defaultdict

class Solution:

	def mostBalloons(self, N, arr):
		if N == 1:
			return 1
		ans = 1
		for i in range(N):
			d = defaultdict(int)
			same = 1
			same_line = 0
			for j in range(N):
				if i == j:
					continue
				if arr[i][0] == arr[j][0]:
					if arr[i][1] == arr[j][1]:
						same += 1
						continue
					else:
						same_line += 1
				else:
					d[(arr[i][1] - arr[j][1]) / (arr[i][0] - arr[j][0])] += 1
			max_d = max(d.values())
			ans = max(ans, same + same_line, same + max_d)
		return ans


import collections

class Solution:

	def mostBalloons(self, N, arr):
		ans = 0
		for i in range(N):
			slopeCount = collections.defaultdict(int)
			count = 0
			(x1, y1) = arr[i]
			for j in range(N):
				(x2, y2) = arr[j]
				if x1 == x2 and y1 == y2:
					count += 1
					continue
				dy = y2 - y1
				dx = x2 - x1
				if dx == 0:
					slopeCount[10 ** 9] += 1
					continue
				slope = dy / dx
				slopeCount[slope] += 1
			for (key, val) in slopeCount.items():
				ans = max(ans, val + count)
		return ans


class Solution:

	def mostBalloons(self, N, arr):
		if N < 3:
			return N
		ans = 0
		count = 0
		for i in range(N):
			x1 = arr[i][0]
			y1 = arr[i][1]
			dic = {'inf': 0}
			count = 0
			for j in range(N):
				x2 = arr[j][0]
				y2 = arr[j][1]
				if x1 == x2 and y1 == y2:
					count += 1
				elif x2 - x1 == 0:
					continue
				else:
					slope = (y2 - y1) / (x2 - x1)
					if slope in dic:
						dic[slope] += 1
					else:
						dic[slope] = 1
			ans = max(ans, max(dic.values()) + count)
		return ans


from collections import defaultdict

class Solution:

	def mostBalloons(self, N, arr):
		mem = defaultdict(int)
		ans = t = cnt = 0
		for i in range(len(arr)):
			mem.clear()
			cnt = 0
			for j in range(len(arr)):
				if arr[j][0] == arr[i][0] and arr[j][1] == arr[i][1]:
					cnt += 1
				elif arr[j][0] == arr[i][0]:
					mem['inf'] = +1
				else:
					t = (arr[j][1] - arr[i][1]) / (arr[j][0] - arr[i][0])
					mem[t] += 1
			ans = max(ans, max(mem.values()) + cnt)
		return ans


class Solution:

	def mostBalloons(self, n, arr):
		dict = {}
		maxpoint = 0
		for i in range(n):
			vertical = 0
			overlap = 1
			curmx = 0
			for j in range(i + 1, n):
				x = arr[j][0] - arr[i][0]
				y = arr[j][1] - arr[i][1]
				if arr[i][0] == arr[j][0] and arr[i][1] == arr[j][1]:
					overlap += 1
				elif x == 0:
					vertical += 1
				else:
					s = y / x
					if s in dict.keys():
						dict[s] = dict[s] + 1
						curmx = max(dict[s], curmx)
					else:
						dict[s] = 1
						curmx = max(dict[s], curmx)
				curmx = max(curmx, vertical)
			maxpoint = max(maxpoint, curmx + overlap)
			dict.clear()
		return maxpoint


class Solution:

	def mostBalloons(self, N, arr):
		ans = 1
		for i in range(N):
			count = {}
			same_pos = 0
			for j in range(N):
				x_diff = arr[j][0] - arr[i][0]
				y_diff = arr[j][1] - arr[i][1]
				if x_diff == 0 and y_diff == 0:
					same_pos += 1
				else:
					slope = float('inf') if y_diff == 0 else x_diff / y_diff
					count[slope] = count.get(slope, 0) + 1
			ans = max(ans, max(count.values()) + same_pos)
		return ans


import math

class Solution:

	def mostBalloons(self, N, arr):
		count = 0
		d = dict()
		m1 = -10 ** 9
		for i in range(N):
			d = dict()
			count = 0
			for j in range(i + 1, N):
				(x1, y1, x2, y2) = (arr[i][0], arr[i][1], arr[j][0], arr[j][1])
				if arr[i] == arr[j]:
					count = count + 1
				if x1 != x2:
					m = (y1 - y2) / (x1 - x2)
					c = x1 * m + y1
					if d.get((m, c)) != None:
						d[m, c] = d[m, c] + 1
					if d.get((m, c)) == None:
						d[m, c] = 2
			l1 = [i for i in d.values()]
			if len(l1) > 0:
				l = max(l1)
				m1 = max(m1, l + count)
		return m1


from collections import defaultdict
import math

class Solution:

	def mostBalloons(self, N, arr):
		res = 1
		for i in range(0, N):
			c = 1
			for j in range(i + 1, N):
				if arr[i] == arr[j]:
					c += 1
			dic = defaultdict(lambda : c)
			for j in range(i + 1, N):
				if arr[i] != arr[j]:
					if arr[j][0] - arr[i][0] == 0:
						temp = math.inf
					else:
						temp = (arr[j][1] - arr[i][1]) / (arr[j][0] - arr[i][0])
					dic[temp] += 1
					res = max(res, dic[temp])
		return res


class Solution:

	def mostBalloons(self, N, arr):
		maxVal = -1
		for i in range(0, len(arr)):
			first1 = arr[i][0]
			second1 = arr[i][1]
			dic = {}
			repeated = 0
			for j in range(0, len(arr)):
				first2 = arr[j][0]
				second2 = arr[j][1]
				if first1 == first2 and second1 == second2:
					repeated += 1
				else:
					if first2 == first1:
						slope = -float('inf')
					else:
						slope = (second2 - second1) / (first2 - first1)
					if slope not in dic:
						dic[slope] = 1
					else:
						dic[slope] += 1
			for value in dic.values():
				maxVal = max(maxVal, value + repeated)
		return maxVal


from collections import defaultdict

class Solution:

	def mostBalloons(self, N, arr):
		if N <= 2:
			return N
		ans = 2
		for i in range(N):
			x = arr[i][0]
			y = arr[i][1]
			c = 0
			mp = defaultdict(int)
			for j in range(N):
				x1 = arr[j][0]
				y1 = arr[j][1]
				if x1 == x and y1 == y:
					c += 1
				else:
					if arr[i][0] == arr[j][0]:
						slope = -float('inf')
					else:
						slope = (y1 - y) / (x1 - x)
					mp[slope] += 1
			for (slope, value) in mp.items():
				ans = max(ans, value + c)
		return ans


class Solution:

	def getSlope(self, a, b):
		x = b[0] - a[0]
		y = b[1] - a[1]
		if x == 0:
			return None
		return y / x

	def mostBalloons(self, N, arr):
		if N <= 1:
			return N
		ans = 1
		for i in range(N):
			h = {}
			same = 1
			for j in range(i + 1, N):
				if arr[i][0] == arr[j][0] and arr[i][1] == arr[j][1]:
					same += 1
					continue
				elif arr[i][0] == arr[j][0]:
					slope = -float('inf')
				else:
					slope = self.getSlope(arr[i], arr[j])
				h[slope] = h.get(slope, 0) + 1
			if len(h) != 0:
				pMax = max(h.values())
			else:
				pMax = 0
			ans = max(same + pMax, ans)
		return ans


inf = float('inf')

class Solution:

	def mostBalloons(self, N, arr):
		freq = {}
		for (x, y) in arr:
			freq[x, y] = freq.get((x, y), 0) + 1
		arr = [*freq.keys()]
		mcs = {}
		for (i, (xi, yi)) in enumerate(arr):
			done = {*{}}
			for (xj, yj) in arr[:i]:
				if xi == xj:
					m = inf
					c = xi
				elif yi == yj:
					m = 0
					c = yi
				else:
					m = (yj - yi) / (xj - xi)
					c = yj - m * xj
				new_line = (m, c)
				if new_line not in done:
					mcs[new_line] = mcs.get(new_line, freq[xj, yj]) + freq[xi, yi]
					done.add(new_line)
		return max(mcs.values())


from collections import defaultdict

class Solution:

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

	def mostBalloons(self, n, a):
		maxb = 0
		for i in range(n):
			(x1, y1) = a[i]
			right = 0
			cur = 1
			d = defaultdict(lambda : 0)
			for j in range(n):
				if i != j:
					(x2, y2) = a[j]
					if x1 == x2:
						right += 1
						if y1 == y2:
							cur += 1
							right -= 1
					else:
						num = abs(y2 - y1)
						den = abs(x2 - x1)
						g = self.gcd(num, den)
						num //= g
						den //= g
						neg = y2 - y1 < 0 and x2 - x1 > 0 or (y2 - y1 > 0 and x2 - x1 < 0)
						d[num, den, neg] += 1
			for (k, v) in d.items():
				maxb = max(maxb, v + cur)
			maxb = max(maxb, right + cur)
		return maxb


class Solution:

	def mostBalloons(self, N, arr):
		if N < 3:
			return N
		max_val = 0
		for i in arr:
			d = {}
			dups = 0
			cur_max = 0
			for j in arr:
				if i != j:
					if j[0] == i[0]:
						slope = 'inf'
					else:
						slope = float(j[1] - i[1]) / float(j[0] - i[0])
					d[slope] = d.get(slope, 0) + 1
					cur_max = max(cur_max, d[slope])
				else:
					dups += 1
			max_val = max(max_val, cur_max + dups)
		return max_val


class Solution:

	def mostBalloons(self, N, arr):
		if N <= 2:
			return N
		maxBalloons = 2
		for i in range(N):
			slope = {}
			(vertical, horizontal, identical) = (0, 0, 0)
			for j in range(N):
				if i != j:
					if arr[i] == arr[j]:
						identical += 1
					elif arr[i][0] == arr[j][0]:
						vertical += 1
					elif arr[i][1] == arr[j][1]:
						horizontal += 1
					else:
						ydiff = arr[i][1] - arr[j][1]
						xdiff = arr[i][0] - arr[j][0]
						gcd = math.gcd(abs(ydiff), abs(xdiff))
						ydiff //= gcd
						xdiff //= gcd
						if xdiff < 0:
							xdiff *= -1
							ydiff *= -1
						if (ydiff, xdiff) in slope:
							slope[ydiff, xdiff] += 1
						else:
							slope[ydiff, xdiff] = 1
			if len(slope):
				maxBalloons = max(maxBalloons, 1 + identical + max(slope.values()))
			maxBalloons = max(maxBalloons, 1 + identical + max(vertical, horizontal))
		return maxBalloons


from math import gcd

class Solution:

	def mostBalloons(self, N, arr):
		if N < 3:
			return N
		ans = 0
		for i in range(N - 1):
			a = arr[i]
			di = {}
			curr = 1
			for j in range(i + 1, N):
				b = arr[j]
				rise = b[1] - a[1]
				run = b[0] - a[0]
				if rise == 0 and run == 0:
					curr += 1
				elif rise == 0 or run == 0:
					if rise:
						s = 10 ** 9 + 1
					else:
						s = 0
					di[s] = di.get(s, 0) + 1
				else:
					s = rise / run
					di[s] = di.get(s, 0) + 1
			for i in di.values():
				ans = max(ans, i + curr)
		return ans
import math
if __name__ == '__main__':
	T = int(input())
	while T > 0:
		N = int(input())
		arr = [[] for j in range(N)]
		for j in range(2):
			inp = [int(i) for i in input().split()]
			for i in range(N):
				arr[i].append(inp[i])
		ob = Solution()
		print(ob.mostBalloons(N, arr))
		T -= 1


class Solution:

	def mostBalloons(self, N, arr):
		if N < 3:
			return N
		ans = 0
		for i in range(N - 1):
			a = arr[i]
			d = {}
			curr = 1
			for j in range(i + 1, N):
				b = arr[j]
				dy = b[1] - a[1]
				dx = b[0] - a[0]
				if dy == 0 and dx == 0:
					curr += 1
				elif dy == 0 or dx == 0:
					if dy == 0:
						slope = 0
					else:
						slope = 10 ** 9 + 1
					d[slope] = d.get(slope, 0) + 1
				else:
					slope = dy / dx
					d[slope] = d.get(slope, 0) + 1
			for i in d.values():
				ans = max(ans, i + curr)
		return ans
import math
if __name__ == '__main__':
	T = int(input())
	while T > 0:
		N = int(input())
		arr = [[] for j in range(N)]
		for j in range(2):
			inp = [int(i) for i in input().split()]
			for i in range(N):
				arr[i].append(inp[i])
		ob = Solution()
		print(ob.mostBalloons(N, arr))
		T -= 1


class Solution:

	def mostBalloons(self, N, arr):
		ma = 0
		if len(arr) < 3:
			return len(arr)
		for i in range(N - 1):
			v = 1
			a = arr[i]
			d = {}
			for j in range(i + 1, N):
				b = arr[j]
				m = b[1] - a[1]
				n = b[0] - a[0]
				if m == 0 and n == 0:
					v += 1
				elif n == 0 or m == 0:
					if m:
						s = 10 ** 9 + 1
					else:
						s = 0
					d[s] = d.get(s, 0) + 1
				else:
					s = m / n
					d[s] = d.get(s, 0) + 1
			for i in d.keys():
				ma = max(ma, d[i] + v)
		return ma

	def fg(self, a, b):
		if b == 0:
			return abs(a)
		else:
			return self.fg(b, a % b)


from collections import defaultdict as dd
import math

class Solution:

	def mostBalloons(self, N, arr):

		def angle(x1, x2, y1, y2):
			dx = x2 - x1
			dy = y2 - y1
			if dx == 0 and dy == 0:
				return 'all'
			if x2 == x1:
				return 'inf'
			h = math.gcd(dx, dy)
			dy /= h
			dx /= h
			return str(dy) + '$' + str(dx)
		max_bursted_ballons = 0
		for i in range(N):
			ballons_at_angle = dd(int)
			curr = 1
			for j in range(N):
				if i == j:
					continue
				a = angle(arr[i][0], arr[j][0], arr[i][1], arr[j][1])
				if a == 'all':
					curr += 1
					continue
				ballons_at_angle[a] += 1
				max_bursted_ballons = max(max_bursted_ballons, ballons_at_angle[a] + curr)
		return max_bursted_ballons


class Solution:

	def mostBalloons(self, N, arr):
		max_points = 0
		if N <= 2:
			return N
		for i in range(len(arr)):
			x1 = arr[i][0]
			y1 = arr[i][1]
			d = {}
			c = 0
			for j in range(len(arr)):
				if i != j:
					x2 = arr[j][0]
					y2 = arr[j][1]
					if x1 == x2 and y1 == y2:
						c += 1
						continue
					if x1 == x2 and y1 != y2:
						slope = float('inf')
					if x1 != x2:
						slope = (y2 - y1) / (x2 - x1)
					if slope in d:
						d[slope] += 1
					if slope not in d:
						d[slope] = 1
			temp_max = 0
			for a in d:
				temp_max = max(temp_max, d[a])
			max_points = max(1 + temp_max + c, max_points)
		return max_points


class Solution:

	def mostBalloons(self, N, arr):
		max_list = []
		max_val = 0
		hashMap = {}
		for i in range(N):
			hashMap = {}
			current_max = 0
			dups = 0
			for j in range(i + 1, N):
				if arr[i] != arr[j]:
					y = arr[j][1] - arr[i][1]
					x = arr[j][0] - arr[i][0]
					try:
						m = y / x
					except:
						m = 'inf'
					hashMap[m] = hashMap.get(m, 1) + 1
					current_max = max(current_max, hashMap[m])
				else:
					dups += 1
			max_val = max(max_val, current_max + dups)
		return max_val


from collections import defaultdict

class Solution:

	def mostBalloons(self, N, arr):
		count_max = 0
		for i in range(len(arr)):
			r_counter = defaultdict(int)
			dups = 0
			(x1, y1) = arr[i]
			cur_max = 0
			for j in range(i + 1, len(arr)):
				(x2, y2) = arr[j]
				if x1 == x2 and y1 == y2:
					dups += 1
					continue
				m = 1.0 * (y2 - y1) / (x2 - x1) if x2 != x1 else 'inf'
				r_counter[m] += 1
				cur_max = max(cur_max, r_counter[m])
			count_max = max(count_max, cur_max + dups)
		return count_max + 1


from collections import defaultdict

class Solution:

	def mostBalloons(self, N, arr):
		res = 0
		if N < 3:
			return N
		else:
			for i in arr:
				max_fre = 0
				dups = 0
				slopes = defaultdict(lambda : 0)
				for j in arr:
					if i != j:
						if i[0] != j[0]:
							slope = float(j[1] - i[1]) / float(j[0] - i[0])
						else:
							slope = 'inf'
						slopes[slope] += 1
						max_fre = max(max_fre, slopes[slope])
					else:
						dups += 1
				res = max(res, max_fre + dups)
			return res


class Solution:

	def mostBalloons(self, N, arr):
		ans = 0
		for i in range(N):
			d = {}
			x1 = arr[i][0]
			y1 = arr[i][1]
			c = 0
			for j in range(N):
				x2 = arr[j][0]
				y2 = arr[j][1]
				if x1 == x2 and y1 == y2:
					c += 1
				elif x1 == x2 and y1 != y2:
					try:
						d[float('inf')] += 1
					except:
						d[float('inf')] = 1
				else:
					slope = (y2 - y1) / (x2 - x1)
					try:
						d[slope] += 1
					except:
						d[slope] = 1
			for i in d:
				ans = max(ans, d[i] + c)
		return ans


class Solution:

	def mostBalloons(self, N, arr):
		maxbal = 0
		for i in range(N):
			my_dict = {}
			samepos = 0
			for j in range(N):
				x_diff = arr[j][0] - arr[i][0]
				y_diff = arr[j][1] - arr[i][1]
				if arr[i] == arr[j]:
					samepos += 1
				else:
					slope = 'inf' if x_diff == 0 else float(y_diff / x_diff)
					my_dict[slope] = my_dict.get(slope, 0) + 1
			maxbal = max(maxbal, max(my_dict.values()) + samepos)
		return maxbal


class Solution:

	def mostBalloons(self, N, arr):
		res = 1
		for i in range(N):
			count = dict()
			same = 0
			for j in range(N):
				x = arr[j][0] - arr[i][0]
				y = arr[j][1] - arr[i][1]
				if x == 0 and y == 0:
					same += 1
				else:
					if y == 0:
						slope = float('inf')
					else:
						slope = x / y
					count[slope] = count.get(slope, 0) + 1
			res = max(res, max(count.values()) + same)
		return res


class Solution:

	def mostBalloons(self, N, arr):
		ans = 0
		for i in range(N):
			d = dict()
			c = 0
			for j in range(N):
				if arr[j][1] == arr[i][1] and arr[j][0] == arr[i][0]:
					c += 1
					continue
				nu = arr[j][1] - arr[i][1]
				de = arr[j][0] - arr[i][0]
				if de == 0:
					slope = 'infinity'
				else:
					slope = nu / de
				if slope not in d:
					d[slope] = 1
				else:
					d[slope] += 1
			for i in d.values():
				ans = max(ans, i + c)
		return ans


class Solution:

	def mostBalloons(self, N, arr):
		result = 0
		for start in arr:
			slopes = {}
			count = 0
			for end in arr:
				if start == end:
					count += 1
				else:
					if start[0] == end[0]:
						slope = 'undefined'
					else:
						slope = (start[1] - end[1]) / (start[0] - end[0])
					if slope in slopes:
						slopes[slope] += 1
					else:
						slopes[slope] = 1
			for i in slopes:
				result = max(result, slopes[i] + count)
		return result


from collections import defaultdict

class Solution:

	def mostBalloons(self, N, arr):
		arr.sort()
		m = 0
		for i in range(len(arr)):
			c = 0
			d = defaultdict(int)
			for j in range(0, len(arr)):
				if arr[i][0] == arr[j][0] and arr[i][1] == arr[j][1]:
					c += 1
				elif arr[i][0] != arr[j][0]:
					d[(arr[j][1] - arr[i][1]) / (arr[j][0] - arr[i][0])] += 1
			for i in d:
				m = max(m, d[i] + c)
		return m


class Solution:

	def mostBalloons(self, N, arr):
		ans = 0
		for i in range(N):
			(x1, y1) = (arr[i][0], arr[i][1])
			count = 0
			infs = 0
			t_ans = 0
			slopes = {}
			for j in range(N):
				(x2, y2) = (arr[j][0], arr[j][1])
				if x1 == x2 and y1 == y2:
					count += 1
					continue
				elif x1 == x2:
					infs += 1
					t_ans = max(t_ans, infs)
					continue
				numerator = y2 - y1
				denominator = x2 - x1
				m = numerator / denominator
				if m not in slopes.keys():
					slopes[m] = 0
				slopes[m] += 1
				t_ans = max(t_ans, slopes[m])
			ans = max(ans, t_ans + count)
		return ans


class Solution:

	def mostBalloons(self, N, arr):
		ans = 0
		for i in range(N):
			x1 = arr[i][0]
			y1 = arr[i][1]
			dic = {}
			count = 0
			for j in range(N):
				x2 = arr[j][0]
				y2 = arr[j][1]
				if x1 == x2 and y1 == y2:
					count += 1
					continue
				if x2 - x1 != 0:
					tan = (y2 - y1) / (1.0 * (x2 - x1))
					if tan not in dic:
						dic[tan] = 0
					else:
						dic[tan] = dic.get(tan) + 1
			for z in dic.keys():
				ans = max(ans, count + dic.get(z))
		return ans + 1


import sys

class Solution:

	def mostBalloons(self, N, arr):
		a = 0
		for i in range(N):
			x1 = arr[i][0]
			y1 = arr[i][1]
			dp = {}
			c = 0
			for j in range(N):
				x2 = arr[j][0]
				y2 = arr[j][1]
				if x2 == x1 and y2 == y1:
					c += 1
					continue
				else:
					if x2 - x1 == 0:
						m = sys.maxsize
					else:
						m = (y2 - y1) / (x2 - x1)
					if m not in dp:
						dp[m] = 1
					else:
						dp[m] += 1
			for k in dp.keys():
				a = max(a, dp[k] + c)
		return a


from collections import Counter

class Solution:

	def mostBalloons(self, n, points):
		if n < 3:
			return n
		max_val = 0
		for i in points:
			d = {}
			dups = 0
			cur_max = 0
			for j in points:
				if i != j:
					if j[0] == i[0]:
						slope = 'inf'
					else:
						slope = float(j[1] - i[1]) / float(j[0] - i[0])
					d[slope] = d.get(slope, 0) + 1
					cur_max = max(cur_max, d[slope])
				else:
					dups += 1
			max_val = max(max_val, cur_max + dups)
		return max_val


class Solution:

	def mostBalloons(self, N, arr):
		if N == 0 or N == 1:
			return N
		ans = 0
		for i in range(N):
			count = 0
			hm = {}
			for j in range(N):
				if arr[j][0] == arr[i][0] and arr[j][1] == arr[i][1]:
					count += 1
					continue
				if arr[j][0] - arr[i][0] != 0:
					slope = (arr[j][1] - arr[i][1]) / (arr[j][0] - arr[i][0])
					hm[slope] = hm.get(slope, 0) + 1
			for (k, v) in hm.items():
				ans = max(ans, v + count)
		return ans


class Solution:

	def mostBalloons(self, N, arr):
		maxx = -float('inf')
		for i in range(0, len(arr)):
			dic = {}
			count = 0
			for j in range(0, len(arr)):
				if arr[j][0] == arr[i][0] and arr[j][1] == arr[i][1]:
					count += 1
					continue
				elif arr[j][0] == arr[i][0]:
					m = float('inf')
				else:
					m = (arr[j][1] - arr[i][1]) / (arr[j][0] - arr[i][0])
				if m in dic.keys():
					dic[m] += 1
				else:
					dic[m] = 1
			maxx = max(maxx, max(dic.values()) + count)
		return maxx


class Solution:

	def mostBalloons(self, N, arr):
		maxx = -float('inf')
		count = 0
		for i in range(0, len(arr)):
			h = {}
			count = 0
			for j in range(0, len(arr)):
				if arr[j][0] == arr[i][0] and arr[j][1] == arr[i][1]:
					count += 1
					continue
				if arr[j][0] == arr[i][0]:
					slope = float('inf')
				else:
					slope = (arr[j][1] - arr[i][1]) / (arr[j][0] - arr[i][0])
				if slope not in h:
					h[slope] = 1
				else:
					h[slope] += 1
			for k in h:
				maxx = max(maxx, h[k] + count)
		return maxx


class Solution:

	def mostBalloons(self, N, arr):
		m = -1
		for i in range(N):
			d = dict()
			co1 = arr[i]
			dups = 0
			for j in range(N):
				if i == j:
					continue
				co2 = arr[j]
				if co1 == co2:
					dups += 1
					continue
				if co1[0] == co2[0]:
					sl = float('inf')
				else:
					sl = (co1[1] - co2[1]) / (co1[0] - co2[0])
				if sl in d:
					d[sl] += 1
				else:
					d[sl] = 2
			t = max(d.values())
			m = max(t + dups, m)
		return m


class Solution:

	def mostBalloons(self, N, points):
		l = len(points)
		m = 0
		for i in range(l):
			dic = {'i': 1}
			same = 0
			for j in range(i + 1, l):
				(tx, ty) = (points[j][0], points[j][1])
				if tx == points[i][0] and ty == points[i][1]:
					same += 1
					continue
				if points[i][0] == tx:
					slope = 'i'
				else:
					slope = (points[i][1] - ty) * 1.0 / (points[i][0] - tx)
				if slope not in dic:
					dic[slope] = 1
				dic[slope] += 1
			m = max(m, max(dic.values()) + same)
		return m


class Solution:

	def mostBalloons(self, N, arr):
		dic = {}
		ans = 0
		for i in range(N):
			a = (arr[i][0], arr[i][1])
			if a in dic:
				dic[a] += 1
			else:
				dic[a] = 1
		d = sorted(dic, reverse=True)
		for i in range(len(d) - 1):
			new_dic = {}
			for j in range(i + 1, len(d)):
				try:
					m = (d[i][1] - d[j][1]) / (d[i][0] - d[j][0])
				except:
					m = d[i][1] - d[j][1]
				if m in new_dic:
					new_dic[m] += dic[d[j]]
				else:
					new_dic[m] = dic[d[i]] + dic[d[j]]
			ans = max(ans, max(new_dic.values()))
		return ans


INF = float('inf')

class Solution:

	def slope(self, p1, p2):
		(x1, y1) = p1
		(x2, y2) = p2
		if y2 == y1:
			return 0
		if x2 == x1:
			return INF
		return (y2 - y1) / (x2 - x1)

	def mostBalloons(self, n, arr) -> int:
		if n <= 2:
			return n
		ans = 0
		for i in range(0, n):
			hm = dict()
			same_slope = 1
			for j in range(i + 1, n):
				val = self.slope(arr[i], arr[j])
				if arr[i] == arr[j]:
					same_slope += 1
				else:
					hm[val] = hm.get(val, 0) + 1
			ans = max(ans, same_slope)
			for k in hm:
				ans = max(ans, hm[k] + same_slope)
		return ans


class Solution:

	def mostBalloons(self, N, arr):
		store = {}
		ans = 0
		for i in range(N):
			f = arr[i][0]
			b = arr[i][1]
			store = {}
			c = 0
			for j in range(N):
				f1 = arr[j][0]
				b1 = arr[j][1]
				if f == f1 and b == b1:
					c += 1
					continue
				else:
					if f1 - f > 0:
						slope = (b1 - b) / (f1 - f)
					else:
						continue
					if slope in store:
						store[slope] += 1
					else:
						store[slope] = 1
			for i in store.keys():
				ans = max(ans, store[i] + c)
		return ans


class Solution:

	def mostBalloons(self, N, arr):
		ans = 1
		for i in range(N):
			count = dict()
			samepos = 0
			for j in range(N):
				xdiff = arr[j][0] - arr[i][0]
				ydiff = arr[j][1] - arr[i][1]
				if xdiff == 0 and ydiff == 0:
					samepos += 1
				else:
					slope = float('inf') if ydiff == 0 else xdiff / ydiff
					count[slope] = count.get(slope, 0) + 1
			ans = max(ans, max(count.values()) + samepos)
		return ans


from collections import defaultdict

class Solution:

	def mostBalloons(self, n, points):
		if n < 3:
			return n
		max_val = 0
		for i in points:
			d = defaultdict(lambda : 0)
			dups = 0
			for j in points:
				if i != j:
					if j[0] == i[0]:
						slope = 'inf'
					else:
						slope = float(j[1] - i[1]) / float(j[0] - i[0])
					d[slope] += 1
				else:
					dups += 1
			for i in d:
				max_val = max(max_val, d[i] + dups)
		return max_val


class Solution:

	def mostBalloons(self, N, arr):
		c = 1
		for x in arr:
			a = 0
			slope = {}
			for y in arr:
				dy = y[1] - x[1]
				dx = y[0] - x[0]
				if x == y:
					a += 1
				else:
					if dx == 0:
						newslope = float('inf')
					else:
						newslope = dy / dx
					slope[newslope] = slope.get(newslope, 0) + 1
			c = max(c, max(slope.values()) + a)
		return c


class Solution:

	def mostBalloons(self, n, a):
		ans = 0
		for i in range(n):
			(c, e) = ({}, 1)
			for j in range(n):
				if i == j:
					continue
				(x, y) = (a[i][0] - a[j][0], a[i][1] - a[j][1])
				if x == 0 and y == 0:
					e += 1
				else:
					if x < 0:
						(x, y) = (-x, -y)
					g = math.gcd(x, abs(y))
					(x, y) = (x // g, y // g)
					c[x, y] = c.get((x, y), 0) + 1
			ans = max(ans, max(c.values()) + e)
		return ans


class Solution:

	def mostBalloons(self, N, arr):
		l = len(arr)
		output = 0
		if N < 3:
			return N
		for i in range(N):
			cur_max = 0
			d = {}
			dups = 0
			for j in range(N):
				if arr[j] != arr[i]:
					if i == j:
						continue
					if arr[j][0] == arr[i][0]:
						slope = 'inf'
					else:
						slope = (arr[j][1] - arr[i][1]) / (arr[j][0] - arr[i][0])
					d[slope] = d.get(slope, 0) + 1
					cur_max = max(cur_max, d[slope])
				else:
					dups += 1
			output = max(cur_max + dups, output)
		return output


class Solution:

	def mostBalloons(self, N, arr):
		ans = 0
		for i in range(N):
			mp = dict()
			samePoint = 0
			for j in range(N):
				if arr[i] == arr[j]:
					samePoint += 1
					continue
				x_diff = arr[j][0] - arr[i][0]
				y_diff = arr[j][1] - arr[i][1]
				slope = float('inf') if x_diff == 0 else y_diff / x_diff
				mp[slope] = mp.get(slope, 0) + 1
			ans = max(ans, max(mp.values()) + samePoint)
		return ans


class Solution:

	def mostBalloons(self, N, arr):
		if N == 1:
			return 1
		answer = 0
		for i in range(N):
			slopes = {}
			count = 0
			for j in range(N):
				p1 = arr[i]
				p2 = arr[j]
				if p1 == p2:
					count += 1
					continue
				elif p2[0] - p1[0] == 0:
					slope = 'inf'
				else:
					slope = (p2[1] - p1[1]) / (p2[0] - p1[0])
				if slope in slopes:
					slopes[slope] += 1
				else:
					slopes[slope] = 1
			for key in slopes:
				answer = max(answer, slopes[key] + count)
		return answer


class Solution:

	def mostBalloons(self, N, XY):
		maxBaloons = 1
		infinity = float('inf')
		for a in range(N):
			samePoints = 0
			Collinear = dict()
			for b in range(N):
				x_Diff = XY[b][0] - XY[a][0]
				y_Diff = XY[b][1] - XY[a][1]
				if x_Diff == 0 and y_Diff == 0:
					samePoints += 1
				else:
					Slope = x_Diff / y_Diff if y_Diff else infinity
					Collinear[Slope] = Collinear.get(Slope, 0) + 1
			maxBaloons = max(max(Collinear.values()) + samePoints, maxBaloons)
		return maxBaloons


class Solution:

	def mostBalloons(self, N, arr):
		ans = 1
		for i in range(N):
			count = dict()
			crp = 0
			for j in range(N):
				ad = arr[j][0] - arr[i][0]
				bd = arr[j][1] - arr[i][1]
				if ad == 0 and bd == 0:
					crp += 1
				else:
					graph = float('infinity') if bd == 0 else ad / bd
					count[graph] = count.get(graph, 0) + 1
			ans = max(ans, max(count.values()) + crp)
		return ans