Input [(3,10),(0,2),(0,2),(3,10)] output 3 expected :4


  • 1
    R

    My code fails for this test case:
    Input: [(3,10),(0,2),(0,2),(3,10)]
    Output: 3
    Expected: 4
    can anyone explain whats wrong? thanks

    import java.util.Comparator;
    import java.util.HashMap;

    public class Solution {

     public static class Line{
        double intercept;
        double slope;
        boolean infinite_line = false;
        double epislon;
        Line(Point p1,Point p2){
            epislon = 0.001;
            if(Math.abs(p1.x - p2.x) >epislon){
                slope = (p1.y -p2.y)/(p1.x-p2.x);
                intercept = p1.y - (slope * p1.x);
            }
            else{
                intercept = p1.x;
                infinite_line = true;
            }
        }
        
       
      
    
        @Override
        public int hashCode() {
            int hash = 7;
            hash = 79 * hash + (int) (Double.doubleToLongBits(this.intercept) ^ (Double.doubleToLongBits(this.intercept) >>> 32));
            hash = 79 * hash + (int) (Double.doubleToLongBits(this.slope) ^ (Double.doubleToLongBits(this.slope) >>> 32));
            hash = 79 * hash + (this.infinite_line ? 1 : 0);
            return hash;
        }
    
        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Line other = (Line) obj;
            if (Double.doubleToLongBits(this.intercept) != Double.doubleToLongBits(other.intercept)) {
                return false;
            }
            if (Double.doubleToLongBits(this.slope) != Double.doubleToLongBits(other.slope)) {
                return false;
            }
            if (this.infinite_line != other.infinite_line) {
                return false;
            }
            if (Double.doubleToLongBits(this.epislon) != Double.doubleToLongBits(other.epislon)) {
                return false;
            }
            return true;
        }
    
        private boolean isEqual(double slope, double slope0) {
            return (Math.abs(slope-slope0)<epislon);
        }
    
    }
     public static int maxPoints(Point[] points) {
        HashMap<Line, HashSet<Point>> map = new HashMap<Line,HashSet<Point>>();
        int maxpoints = 0;
        if(points.length==1) return 1;
        for(int i=0;i<points.length;i++){
            for(int j=i+1;j<points.length;j++){
                HashSet<Point> set = new HashSet<Point>();
                
                set.add(points[i]);
                set.add(points[j]);
                Line line = new Line(points[i],points[j]);
                if(!map.containsKey(line)){
                    map.put(line,set );
                }
                else{
                    HashSet<Point>set1 = map.get(line);
                    set1.addAll(set);
                    
                    map.put(line, set1);
                    
                }
                if(maxpoints < map.get(line).size()){
                        maxpoints = map.get(line).size();
                        
                    }
                
            }
        }
        
        return maxpoints;
        
    }
    

    }


  • 0
    S

    Please format your code correctly. Share some words about your algorithm and add comment in your code.


  • 0
    M

    I believe what has happened is that the duplicated (3,10) point at the end is not registering as being on the same line as (3,10),(0,2),(0,2), which has a slope of 0.325. This would cause the "max" number of points to be 3 instead of the correct 4.


Log in to reply
 

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