-
Notifications
You must be signed in to change notification settings - Fork 0
/
maxPointsOnALine.py
98 lines (88 loc) · 6.49 KB
/
maxPointsOnALine.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
# Definition for a point
class Point:
def __init__(self, a=0, b=0):
self.x = a
self.y = b
def __eq__(self, other):
return isinstance(other, self.__class__) and self.x == other.x and self.y == other.y
def __hash__(self):
return hash(self.x) ^ hash(self.y)
def __str__(self):
return "(%s, %s)" % (self.x, self.y)
import collections
import time
import math
class Solution:
# @param points, a list of Points
# @return an integer
def maxPoints(self, points):
# start = time.clock()
if len(points) <= 2:
return len(points)
original = points[:]
# points = list(set(points))
temp = []
extra = []
for i in points:
if i not in temp:
temp.append(i)
else:
extra.append(i)
points = temp
all_combi = []
l = len(points)
for i in range(l-1):
for j in range(i+1, l):
p1 = points[i]
p2 = points[j]
# all_combi.append((p1, p2))
all_combi.append(collections.Counter([p1, p2]))
mcDict = dict()
# print all_combi
for c in all_combi:
c = list(c.elements())
p1, p2 = c[0], c[1]
m, c = self.getAngle(p1, p2)
if (m, c) not in mcDict:
mcDict[(m, c)] = [p1, p2]
else:
if p1 not in mcDict[(m, c)]:
mcDict[(m, c)].append(p1)
if p2 not in mcDict[(m, c)]:
mcDict[(m, c)].append(p2)
if mcDict != {}:
finalMax = max([len(i) for i in mcDict.values()])
for k, v in mcDict.iteritems():
if len(v) == finalMax:
# print [str(i) for i in v]
# print k
tempMax = finalMax
for x in v:
cnt = extra.count(x)
if cnt == 1:
tempMax += cnt
finalMax = tempMax
break
# else:
# finalMax = len(original)
# print time.clock()-start
return finalMax
def getAngle(self, point1, point2):
vertical = abs(float(point1.x - point2.x)) <= 0.00000001
if vertical:
m = 90
else:
m = math.degrees(math.atan((point1.y - point2.y)/float(point1.x - point2.x)))
c = point1.y - m * point1.x
return m, c
# points = [(0,-12),(5,2),(2,5),(0,-5),(1,5),(2,-2),(5,-4),(3,4),(-2,4),(-1,4),(0,-5),(0,-8),(-2,-1),(0,-11),(0,-9)]
points = [(-240,-657),(-27,-188),(-616,-247),(-264,-311),(-352,-393),(-270,-748),(3,4),(-308,-87),(150,526),(0,-13),(-7,-40),(-3,-10),(-531,-892),(-88,-147),(4,-3),(-873,-555),(-582,-360),(-539,-207),(-118,-206),(970,680),(-231,-47),(352,263),(510,143),(295,480),(-590,-990),(-236,-402),(308,233),(-60,-111),(462,313),(-270,-748),(-352,-393),(-35,-148),(-7,-40),(440,345),(388,290),(270,890),(10,-7),(60,253),(-531,-892),(388,290),(-388,-230),(340,85),(0,-13),(770,473),(0,73),(873,615),(-42,-175),(-6,-8),(49,176),(308,222),(170,27),(-485,-295),(170,27),(510,143),(-18,-156),(-63,-316),(-28,-121),(396,304),(472,774),(-14,-67),(-5,7),(-485,-295),(118,186),(-154,-7),(-7,-40),(-97,-35),(4,-9),(-18,-156),(0,-31),(-9,-124),(-300,-839),(-308,-352),(-425,-176),(-194,-100),(873,615),(413,676),(-90,-202),(220,140),(77,113),(-236,-402),(-9,-124),(63,230),(-255,-118),(472,774),(-56,-229),(90,228),(3,-8),(81,196),(970,680),(485,355),(-354,-598),(-385,-127),(-2,7),(531,872),(-680,-263),(-21,-94),(-118,-206),(616,393),(291,225),(-240,-657),(-5,-4),(1,-2),(485,355),(231,193),(-88,-147),(-291,-165),(-176,-229),(154,153),(-970,-620),(-77,33),(-60,-111),(30,162),(-18,-156),(425,114),(-177,-304),(-21,-94),(-10,9),(-352,-393),(154,153),(-220,-270),(44,-24),(-291,-165),(0,-31),(240,799),(-5,-9),(-70,-283),(-176,-229),(3,8),(-679,-425),(-385,-127),(396,304),(-308,-352),(-595,-234),(42,149),(-220,-270),(385,273),(-308,-87),(-54,-284),(680,201),(-154,-7),(-440,-475),(-531,-892),(-42,-175),(770,473),(118,186),(-385,-127),(154,153),(56,203),(-616,-247)]
# points = [(1,1),(1,1),(1,1),(0,0),(1,2)]
# points = [(-4,-4),(-8,-582),(-3,3),(-9,-651),(9,591)]
# points = [(40,-23),(9,138),(429,115),(50,-17),(-3,80),(-10,33),(5,-21),(-3,80),(-6,-65),(-18,26),(-6,-65),(5,72),(0,77),(-9,86),(10,-2),(-8,85),(21,130),(18,-6),(-18,26),(-1,-15),(10,-2),(8,69),(-4,63),(0,3),(-4,40),(-7,84),(-8,7),(30,154),(16,-5),(6,90),(18,-6),(5,77),(-4,77),(7,-13),(-1,-45),(16,-5),(-9,86),(-16,11),(-7,84),(1,76),(3,77),(10,67),(1,-37),(-10,-81),(4,-11),(-20,13),(-10,77),(6,-17),(-27,2),(-10,-81),(10,-1),(-9,1),(-8,43),(2,2),(2,-21),(3,82),(8,-1),(10,-1),(-9,1),(-12,42),(16,-5),(-5,-61),(20,-7),(9,-35),(10,6),(12,106),(5,-21),(-5,82),(6,71),(-15,34),(-10,87),(-14,-12),(12,106),(-5,82),(-46,-45),(-4,63),(16,-5),(4,1),(-3,-53),(0,-17),(9,98),(-18,26),(-9,86),(2,77),(-2,-49),(1,76),(-3,-38),(-8,7),(-17,-37),(5,72),(10,-37),(-4,-57),(-3,-53),(3,74),(-3,-11),(-8,7),(1,88),(-12,42),(1,-37),(2,77),(-6,77),(5,72),(-4,-57),(-18,-33),(-12,42),(-9,86),(2,77),(-8,77),(-3,77),(9,-42),(16,41),(-29,-37),(0,-41),(-21,18),(-27,-34),(0,77),(3,74),(-7,-69),(-21,18),(27,146),(-20,13),(21,130),(-6,-65),(14,-4),(0,3),(9,-5),(6,-29),(-2,73),(-1,-15),(1,76),(-4,77),(6,-29)]
# points = [(29,87),(145,227),(400,84),(800,179),(60,950),(560,122),(-6,5),(-87,-53),(-64,-118),(-204,-388),(720,160),(-232,-228),(-72,-135),(-102,-163),(-68,-88),(-116,-95),(-34,-13),(170,437),(40,103),(0,-38),(-10,-7),(-36,-114),(238,587),(-340,-140),(-7,2),(36,586),(60,950),(-42,-597),(-4,-6),(0,18),(36,586),(18,0),(-720,-182),(240,46),(5,-6),(261,367),(-203,-193),(240,46),(400,84),(72,114),(0,62),(-42,-597),(-170,-76),(-174,-158),(68,212),(-480,-125),(5,-6),(0,-38),(174,262),(34,137),(-232,-187),(-232,-228),(232,332),(-64,-118),(-240,-68),(272,662),(-40,-67),(203,158),(-203,-164),(272,662),(56,137),(4,-1),(-18,-233),(240,46),(-3,2),(640,141),(-480,-125),(-29,17),(-64,-118),(800,179),(-56,-101),(36,586),(-64,-118),(-87,-53),(-29,17),(320,65),(7,5),(40,103),(136,362),(-320,-87),(-5,5),(-340,-688),(-232,-228),(9,1),(-27,-95),(7,-5),(58,122),(48,120),(8,35),(-272,-538),(34,137),(-800,-201),(-68,-88),(29,87),(160,27),(72,171),(261,367),(-56,-101),(-9,-2),(0,52),(-6,-7),(170,437),(-261,-210),(-48,-84),(-63,-171),(-24,-33),(-68,-88),(-204,-388),(40,103),(34,137),(-204,-388),(-400,-106)]
points = [Point(x[0], x[1]) for x in points]
point1 = Point(0,0)
point2 = Point(0,0)
sol = Solution()
print sol.maxPoints(points)