class Solution:
def get_line_equation(self, p1, p2):
x1, y1 = p1
x2, y2 = p2
x1 = float(x1)
y1 = float(y1)
return (y2y1, (x2x1), (x2x1)*y1(y2y1)*x1)
def get_line_hash(self, p1, p2):
a, b, c = self.get_line_equation(p1, p2)
if b == 0:
if a == 0: return ""
slope = "inf"
inter = "%.6f" % round(c / a, 6)
else:
slope = "%.6f" % round(a / b, 6)
inter = "%.6f" % round(c / b, 6)
return "%s %s" % (slope, inter)
# @param points, a list of Points
# @return an integer
def maxPoints(self, points):
ans = 1 if points else 0
count = collections.defaultdict(set)
for i in range(len(points)):
for j in range(i + 1, len(points)):
line_hash = self.get_line_hash((points[i].x, points[i].y), (points[j].x, points[j].y))
count[line_hash].add(points[i])
count[line_hash].add(points[j])
if ans < len(count[line_hash]): ans = len(count[line_hash])
return ans
O(n^2) TLE for python??


def get_line_hash(self, p1, p2): a, b, c = self.get_line_equation(p1, p2) if b == 0: if a == 0: return "" slope = "inf" inter = "%.6f" % round(c / a, 6) else: slope = "%.6f" % round(a / b, 6) inter = "%.6f" % round(c / b, 6) return "%s %s" % (slope, inter)
Parsing float to str would be very slow. I remove the
(%s %s) %
part in the return statement, TLE has gone but it appears to be WA.