leetcode-go/leetcode/hard/149.max-points-on-a-line.java

import java.util.HashMap;

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
class Solution {
    class Pair {
        final int _1;
        final int _2;

        Pair(int _1, int _2) {
            this._1 = _1;
            this._2 = _2;
        }

        @Override
        public int hashCode() {
            int hash = 7;
            hash = 71 * hash + _1;
            hash = 71 * hash + _2;
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (!(obj instanceof Pair)) return false;
            Pair p = (Pair) obj;
            return p._1 == _1 && p._2 == _2;
        }
    }

    public int maxPoints(Point[] points) {
        int res = 0;
        for (int i = 0; i < points.length; i++) {
            HashMap<Pair, Integer> map = new HashMap<>();
            int cnt = 1;
            for (int j = 0; j < points.length; j++) {
                if (j == i) continue;
                Point p1 = points[i];
                Point p2 = points[j];
                if (p1.x == p2.x && p1.y == p2.y) {
                    cnt++;
                    continue;
                }
                Pair slope = getSlope(p1, p2);
                Integer freq = map.getOrDefault(slope, 0);
                map.put(slope, freq + 1);
            }
            int max = 0;
            for (Integer val : map.values()) {
                max = Math.max(max, val);
            }
            res = Math.max(res, max + cnt);
        }
        return res;
    }

    private Pair getSlope(Point p1, Point p2) {
        int dx = p1.x - p2.x;
        int dy = p1.y - p2.y;
        if (dx == 0) return new Pair(p1.x, 0);
        if (dy == 0) return new Pair(0, p1.y);
        int d = gcd(dx, dy);
        return new Pair(dx / d, dy / d);
    }

    private int gcd(int m, int n) {
        return n == 0 ? m : gcd(n, m % n);
    }
}