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:
Post a Comment