LeetCode -- Max Points on a Line

LeetCode -- Max Points on a Line

題目描述：


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






思路：
這算是一道數學題，關鍵在於存方程，把點一一代入判斷是否滿足。


1. 兩層循環遍歷節點O，存直線方程的關鍵因子：斜率：K, 截距：B，X：X軸截距（K為無窮時），Y:Y軸截距（K為0時）。
2. 對每個方程分別遍歷每個點，找到滿足最多點的方程即可。


注：在小於精度0.00001時，本解法有Bug


實現代碼：

 /**
 * Definition for a point.
 * public class Point {
 *     public int x;
 *     public int y;
 *     public Point() { x = 0; y = 0; }
 *     public Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int MaxPoints(Point[] points) 
    {
     	if(points.Length == 0){
    		return 0;
    	}
    	if(points.Length < 2){
    		return 1;
    	}
     	
    	// 1. same line functions into list
    	var funcs = new Dictionary();
    	
    	for(var i = 0;i < points.Length; i++){
    		for(var j = 0; j < points.Length;j ++){
    			if(i != j){
    				var line = Line(points[i], points[j]);
    				var k = line.ToString();
    				if(!funcs.ContainsKey(k)){
    					funcs.Add(k,line);
    				}
    			}
    		}
    	}


    	// 2. loop each function , count how many points can fulfil
    	var max = 0;
    	foreach(var k in funcs.Keys){
    		var c = 0;
    		for(var i = 0;i < points.Length; i++){
    			if(funcs[k].Test(points[i])){
    				c++;
    			}
    		}
    		if(c > max){
    			max = c;
    		}
    	}
    	
    	return max;
    }


private LineFunc Line(Point p1 , Point p2){
	double deltaX = p1.x - p2.x;
	var k = deltaX == 0 ? int.MaxValue : ((p1.y - p2.y) / deltaX);
	var b = p1.y - k * p1.x;
	
	return new LineFunc(k,b,p1.x,p1.y);
}


public class LineFunc{


	public LineFunc(double k , double b, double x0, double y0){
		K = k;
		if(k == 0){
			Y = y0;
		}
		else if(k == int.MaxValue){
			X = x0;
		}
		else{
			B = b;
		}
	}
	
	public bool Test(Point p){
		if(K == int.MaxValue){
			return p.x == X;
		}
		else if(K == 0){
			return p.y == Y;
		}
		else{
			var delta = p.y - (p.x * K + B);
			return delta < 0.00001 && delta > -0.000001;
		}
	}
	
	public double K;
	public double Y;
	public double X;
	public double B;
	
	public override string ToString(){
		return string.Format({0}_{1}_{2}_{3}, K, B, X, Y);
	}
}




}