给出二维平面上的n个点，求最多有多少点在同一条直线上。
这道题搞得我非常恼火，很早以前就做出来了，一直都是WA，但是我一直找不到算法的问题，今天突然灵机一动，给我找到问题所在了，原来的代码是这样的：
/**
* Definition for a point.
* class Point {
* int x;
* int y;
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
* }
*/
public class Solution {
/**
* @param points an array of point
* @return an integer
*/
public int maxPoints(Point[] points) {
// Write your code here
if (points==null){
return 0;
}else if(points.length==0||points.length==1||points.length==2){
return points.length;
}else
{
int max = 0;
int count;
double[] result;
for (int i =0;i<points.length;i++)
{
for(int j=i+1;j<points.length;j++)
{
count = 0;
if(points[i].x==points[j].x)
{
for(int m=0;m<points.length;m++)
{
if (points[m].x==points[i].x)
count++;
}
}
else
{
result = calcF(points[i],points[j]);
for(int k =0;k<points.length;k++)
{
if(result[0]*points[k].x+result[1]==(double)points[k].y)
count++;
}
}
max=count>max?count:max;
}
}
return max;
}
}
public double[] calcF(Point a,Point b){
double[] i =new double[2];
i[0]=(double)(a.y-b.y)/(double)(a.x-b.x);
i[1]=(double)a.y-(double)a.x*i[0];
return i;
}
}
原理很简单，每个点两两之间计算斜率和截距，算出直线方程，再把每个点往方程里套。符合方程的即在一条直线上，在求出最大值即可。
但是为什么错了呢？
原因就是：Double的精度问题！！！
由于计算机存储double无法保留足够的精度，所以在一长串double的显性转换中，精度丢失的很厉害。
在这里计算方程的时候不能按照原来数学上的直接把斜率和截距作为方程的参数了，为了保证精度，我们需要将斜率k写成diffY/diffX，然后为了在计算斜率时不作处罚，计算出的应该是diffX倍的斜率，最后calcF方程应写作：
int difX = points[i].x -points[j].x;
int difY = points[i].y -points[j].y;
int intercept = points[i].y*difX - points[i].x*difY;
最后套入判别式应该是：
for(int k =0;k<points.length;k++)
{
if(points[k].x*difY + intercept == points[k].y * difX)
count++;
}
这样所有参与运算的数都是整数，将不会存在精度问题。
