Max Points on a Line

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        if (n <= 2) return n;
        int ans = 1;
        for (int i = 0; i < n; ++i) {
            unordered_map<long long, int> mp;
            int local = 0;
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];
                int g = __gcd(abs(dx), abs(dy));
                if (g == 0) g = 1;
                dx /= g; dy /= g;
                if (dx < 0 || (dx == 0 && dy < 0)) { dx = -dx; dy = -dy; }
                long long key = ((long long)dx << 20) ^ ((long long)(unsigned)dy);
                local = max(local, ++mp[key]);
            }
            ans = max(ans, local + 1);
        }
        return ans;
    }
};

func maxPoints(points [][]int) int {
    n := len(points)
    if n <= 2 {
        return n
    }
    abs := func(x int) int {
        if x < 0 {
            return -x
        }
        return x
    }
    var gcd func(a, b int) int
    gcd = func(a, b int) int {
        if b == 0 {
            return a
        }
        return gcd(b, a%b)
    }
    ans := 1
    for i := 0; i < n; i++ {
        mp := make(map[int64]int)
        local := 0
        for j := 0; j < n; j++ {
            if i == j {
                continue
            }
            dx := points[j][0] - points[i][0]
            dy := points[j][1] - points[i][1]
            g := gcd(abs(dx), abs(dy))
            if g == 0 {
                g = 1
            }
            dx /= g
            dy /= g
            if dx < 0 || (dx == 0 && dy < 0) {
                dx = -dx
                dy = -dy
            }
            key := int64(dx)<<20 ^ int64(uint32(dy))
            mp[key]++
            if mp[key] > local {
                local = mp[key]
            }
        }
        if local+1 > ans {
            ans = local + 1
        }
    }
    return ans
}

from collections import defaultdict
from math import gcd
from typing import List

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        if n <= 2:
            return n
        ans = 1
        for i in range(n):
            mp: dict = defaultdict(int)
            local = 0
            for j in range(n):
                if i == j:
                    continue
                dx = points[j][0] - points[i][0]
                dy = points[j][1] - points[i][1]
                g = gcd(abs(dx), abs(dy))
                if g == 0:
                    g = 1
                dx //= g
                dy //= g
                if dx < 0 or (dx == 0 and dy < 0):
                    dx, dy = -dx, -dy
                key = (dx, dy)
                mp[key] += 1
                if mp[key] > local:
                    local = mp[key]
            if local + 1 > ans:
                ans = local + 1
        return ans

function maxPoints(points) {
    const n = points.length;
    if (n <= 2) return n;
    const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
    let ans = 1;
    for (let i = 0; i < n; i++) {
        const mp = new Map();
        let local = 0;
        for (let j = 0; j < n; j++) {
            if (i === j) continue;
            let dx = points[j][0] - points[i][0];
            let dy = points[j][1] - points[i][1];
            let g = gcd(Math.abs(dx), Math.abs(dy));
            if (g === 0) g = 1;
            dx = Math.trunc(dx / g);
            dy = Math.trunc(dy / g);
            if (dx < 0 || (dx === 0 && dy < 0)) { dx = -dx; dy = -dy; }
            const key = `${dx},${dy}`;
            const c = (mp.get(key) || 0) + 1;
            mp.set(key, c);
            if (c > local) local = c;
        }
        if (local + 1 > ans) ans = local + 1;
    }
    return ans;
}

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if (n <= 2) return n;
        int ans = 1;
        for (int i = 0; i < n; i++) {
            Map<Long, Integer> mp = new HashMap<>();
            int local = 0;
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];
                int g = gcd(Math.abs(dx), Math.abs(dy));
                if (g == 0) g = 1;
                dx /= g;
                dy /= g;
                if (dx < 0 || (dx == 0 && dy < 0)) {
                    dx = -dx;
                    dy = -dy;
                }
                long key = ((long) dx << 20) ^ ((long)(dy & 0xFFFFFFFFL));
                int c = mp.getOrDefault(key, 0) + 1;
                mp.put(key, c);
                if (c > local) local = c;
            }
            if (local + 1 > ans) ans = local + 1;
        }
        return ans;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

function maxPoints(points: number[][]): number {
    const n = points.length;
    if (n <= 2) return n;
    const gcd = (a: number, b: number): number => b === 0 ? a : gcd(b, a % b);
    let ans = 1;
    for (let i = 0; i < n; i++) {
        const mp = new Map<string, number>();
        let local = 0;
        for (let j = 0; j < n; j++) {
            if (i === j) continue;
            let dx = points[j][0] - points[i][0];
            let dy = points[j][1] - points[i][1];
            let g = gcd(Math.abs(dx), Math.abs(dy));
            if (g === 0) g = 1;
            dx = Math.trunc(dx / g);
            dy = Math.trunc(dy / g);
            if (dx < 0 || (dx === 0 && dy < 0)) { dx = -dx; dy = -dy; }
            const key = `${dx},${dy}`;
            const c = (mp.get(key) ?? 0) + 1;
            mp.set(key, c);
            if (c > local) local = c;
        }
        if (local + 1 > ans) ans = local + 1;
    }
    return ans;
}