题解 | 多少个点位于同一直线

import java.util.*;

/*
 * public class Point {
 *   int x;
 *   int y;
 * }
 */

public class Solution {
    /**
     *
     * @param points Point类一维数组
     * @return int整型
     */
    public int maxPoints (Point[] points) {
        // write code here
        int n = points.length;
        if (n <= 2) {
            return n;
        }
        int maxCount = 0;
        for (int i = 0; i < n; i++) {
            Map<String, Integer> slopeMap = new HashMap<>();
            int duplicate = 0;
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (points[i].x == points[j].x && points[i].y == points[j].y) {
                    duplicate++;
                    continue;
                }
                int dx = points[j].x - points[i].x;
                int dy = points[j].y - points[i].y;
                String slopeKey;
                if (dx == 0) {
                    slopeKey = "0,1";
                } else if (dy == 0) {
                    slopeKey = "1,0";
                } else {
                    int g = gcd(Math.abs(dx), Math.abs(dy));
                    dx /= g;
                    dy /= g;
                    if (dy < 0) {
                        dx = -dx;
                        dy = -dy;
                    }
                    slopeKey = dx + "," + dy;
                }
                slopeMap.put(slopeKey, slopeMap.getOrDefault(slopeKey, 0) + 1);
            }
            int currentMax = 0;
            for (int count : slopeMap.values()) {
                if (count > currentMax) {
                    currentMax = count;
                }
            }
            currentMax += duplicate + 1;
            if (currentMax > maxCount) {
                maxCount = currentMax;
            }
        }
        return maxCount;
    }
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }


}