# Is there a possible N^2 algorithm if points are in float?

• As most of the N^2 method is using harsh map with calculating the GCD, I wonder if it is possible to have an algorithm that doesn't utilize the integer characteristics.

• Expected O(N^2) algorithm using map, assuming that hash query can be finished in O(1) for pairs of floats.

``````class Solution:
# @param points, a list of Points
# @return an integer
def maxPoints(self, points):
if len(points) == 0: return 0
points = [(p.x, p.y) for p in points]
d = collections.defaultdict(lambda: 0)
for p in points: d[p] += 1
length = len(points)
unique_points = list(set(points))
number_points = len(unique_points)
if number_points == 1: return len(points)
lines = collections.defaultdict(set)
for i in xrange(number_points):
for j in xrange(i+1, number_points):
if unique_points[i][0] == unique_points[j][0]:
k = float('inf')
b = unique_points[i][0]
else:
k = float(unique_points[i][1] - unique_points[j][1]) / (unique_points[i][0] - unique_points[j][0])
b = float(unique_points[i][0] * unique_points[j][1] - unique_points[j][0] * unique_points[i][1]) / (unique_points[i][0] - unique_points[j][0])