PPaste!

max_points_on_a_line.py

Home - All the pastes - Authored by Thooms

Raw version

 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
from collections import defaultdict

def gradient(a, b):
    if a.x == b.x:
        return float('inf')
    return float(a.y - b.y) / float(a.x - b.x)

class Solution(object):
    def maxPoints(self, points):
        if len(points) < 2:  # because fuck you
            return len(points)

        m = 2
        for a in points:
            gradients = defaultdict(int)
            same = 0
            for b in points:
                if (a.x == b.x) and (a.y == b.y):  # because fuck you, too
                    same += 1
                else:
                    gradients[gradient(a, b)] += 1
            
            _m = same
            if len(gradients):
                _m += max(gradients.values())
            m = max(m, _m)

        return m