Java code using self-defined Line


  • 0
    H

    Basically I use a map to track all the points on every line.
    Since a line is defined as y = ax + b, a line can be identified using slope and intersection. For hash's sake, we gotta define hashCode and equals methods ourselves.

    /**
     * Definition for a point.
     * class Point {
     *     int x;
     *     int y;
     *     Point() { x = 0; y = 0; }
     *     Point(int a, int b) { x = a; y = b; }
     * }
     */
    public class Solution {
        private class Line {
            double slope, intersect;
            Line(Point a, Point b) {
                if (a.x == b.x) {
                    slope = Double.POSITIVE_INFINITY;
                    intersect = a.x;
                }
                else {
                    slope = (b.y - a.y) / (double)(b.x - a.x);
                    // slope = Math.round(100 * slope) / 100;
                    // Due to the precision problem, the order of 
                    // a and b matters. To avoid this problem, use
                    // both a and b to calculate intersection.
                    intersect = (a.y * b.x - b.y * a.x) / (double) (b.x-a.x);
                    // intersect = a.y - slope * a.x;
                    // intersect = b.y - slope * b.x;
                    // intersect = a.y - slope * a.x + b.y - slope * a.y;
                    // intersect = Math.round(100 * intersect) / 100;
                }
            }
            @Override
            public int hashCode() {
                if (slope == Double.POSITIVE_INFINITY)
                    return (int) intersect;
                else
                    return (int) (slope * 31 + intersect);
            }
            @Override
            public boolean equals(Object other) {
                Line that = (Line) other;
                return this.slope == that.slope 
                    && this.intersect == that.intersect;
            } 
        }
        
        public int maxPoints(Point[] points) {
            int result = 0;
            if (points.length < 2) return points.length;
            Map<Line, Set<Point>> map = new HashMap();
            for (int i = 0; i < points.length-1; i++) {
                for (int j = i+1; j < points.length; j++) {
                    Line line = new Line(points[i], points[j]);
                    Set<Point> set = map.get(line);
                    if (set == null) {
                        set = new HashSet();
                        map.put(line, set);
                    }
                    set.add(points[i]);
                    set.add(points[j]);
                    result = Math.max(result, set.size());
                }
            }
            return result;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.