Problem

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

JavaScript Code

var Point = function (xPos, yPos) {
    this.x = xPos;
    this.y = yPos;
}
function maxPoints(points) {
    if(points == null || points.length == 0) return 0;
 
    var result = {};
    var max=0;
 
    for(var i=0; i<points.length; i++){
        var duplicate = 1;//
        var vertical = 0;
        for(var j=i+1; j<points.length; j++){
            //handle duplicates and vertical
            if(points[i].x == points[j].x){
                if(points[i].y == points[j].y){
                    duplicate++;
                }else{
                    vertical++;
                }
            }else{
                var slope = points[j].y == points[i].y ? 0.0 : (1.0 * (points[j].y - points[i].y)) / (points[j].x - points[i].x);
                if(result[slope] != null){
                    result[slope] = result[slope] + 1;
                }else{
                    result[slope] = 1;
                }
            }
        }
 
        for(var slope in result){
            var count = result[slope];
            if(count+duplicate > max){
                max = count+duplicate;
            }
        }
 
        max = Math.max(vertical + duplicate, max);
        result = {};
    }
    return max;
}

var points = [
              new Point(2,0),
              new Point(4,0),
              new Point(6,0),
              new Point(7,0),
              new Point(0,1),
              new Point(0,4),
              new Point(0,6),
              new Point(1,1),
              new Point(2,2),
              new Point(4,4),
              new Point(6,6)
              ]
console.log(maxPoints(points));

0 comments:

Blogroll

Follow this blog by Email

Popular Posts