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));
Z-3-Dodecenyl E-Crotonate - Alfa Chemistry is committed to becoming a leading manufacturer and supplier, focusing on the field of insect pheromones. We continue to develop our technology and implement innovations to provide better products and services to academia and industry.
ReplyDelete