前言：只是为了加深自己对面试题的领悟力，如果有做的错的，请指出，感激。
微软面试题：从给定点集中，找到所有的在一条直线的三个点，用三元组记录。
算法概要：最一般的算法是遍历所有的点，三重循环，判断三个点的斜率是否相等或者向量的叉积是否为零。时间复杂为O（N3）。
我好像找到了一个上限是O（N2LogN）的算法。
假设平面上有三个点A，B，C。三点互相连接的话一定有三条直线。
A 点存储 Kab,Kac.（代表斜率的意思）
B 点存储Kbc
C 点什么也不存储。
一条直线连接两个点，因此A点存储直线AB的斜率时，B点就不用存储了。如果A点存储的Kab和Kac相等，那么就代表A，B，C在一条直线上就可以形成一个三元组。
如果再在平面上添加一个点D，应该是依次求D与A，B，C连线直线的斜率，并存储到相应的位置。
A 点存储 Kab,Kac,Kad（代表斜率的意思）
B 点存储Kbc,Kbd
C 点存储Kcd
D 点什么也不存储。
点集A和B，B的初始值为空，A保存平面中所有点集，每次从A中取出一个点p，与B中的所有点求斜率后放入点集B，直到A为空。
求两点斜率和保存斜率问题
假设平面中点的数量为n，对于A点要求（n-1）次的斜率，对于B点要求（n-2）次的斜率，……最后一个点不用求斜率，因此求斜率要O(N2)的时间复杂度。
对于集合A中的第一个点，它关联的斜率就是K12,K13…K1n,共计n-1个点，第二个点关联的斜率为K23,K24…K2n-1共计n-2个点….在算法实现时，可以利用这个规律。
查找某一点关联的斜率集合中，斜率相同的元素。
求完斜率之后对A点关联的斜率进行遍历查找，如果存在相同的斜率那么就是代表找到了一个三元组（要考虑3个以上的点在一条直线的情况）。如果不排序的话时间复杂度是
O(N2)，总的时间复杂度就是 1的平方+2的平方+3的平方+…=（N-1）的平方，时间复杂度大概也是O(N3)的级别的。
如果排序的话查找斜率相同的元素数时间复杂度为O（N+m）N是斜率集合的长度，假设斜率集合中某一个斜率元素相同的个数为K，它可以组合的三元组为K*(k-1)/2的个数，m是集合中所有的三元组的个数。M的值还真不好估计，K=N时取最大，数量级为O(N2).一般情况下不会大于N（这个没有数学依据，我瞎说的）。
如果采用快速（希尔，归并）排序的话，排序的时间复杂度O（NlogN）。
如果不考虑O（N+m）m量级N2的情况。对集合A所有点相关联的斜率排序的时间复杂度为：1log1+2log2+3log3+….+(N-1)log(N-1)<log(n-1)(1+2+3+4+…..+N-1),因此时间复杂度的上限为O(N2LogN).
算法的C#代码实现部分，请先看下面的图（可以另存为图片，这样看的比较舒服一些）。
Trip是一个结构体，代表三元组。
PointFactory是一个专门负责生产平面上点集的类，是一个完全的静态类，对外提供两个接口：一个是点集的数量，另外一个是根据索引给出点集的XY坐标，如果索引大于点集数量则返回false，否则返回true并返回XY坐标。
IFindLineHelper是一个接口，主要有一个函数，List<Trip> GetTripTuple(int start, int mainIndex); mainIndex 是平面上点集合指向某点的一个索引，要求的就是这个点与集合中满足某些条件的点链接直线段的斜率，条件就是：集合中点集的索引index>= start，（主要就是前面所说的从集合A中取出某一点p，放到B中，mainIndex就是点p，start之后就是要与点p计算斜率的点，mainIndex之前的点已经求出），返回的三元组。
FindLineHelper是IFindLineHelper实现类，它主要私有方法：一个是计算与这个点关联的斜率，另一个就是对这些斜率进行排序（要注意他们的斜率和索引信息保持一致），因此成员变量除了一个斜率数组外slopeArr，还有一个索引数组IndexArr。ERROR是个常量代表当两个直线斜率的差的绝对值小于ERROR时，就认为斜率是一样的，避免计算误差。点的坐标XY的类型是Int主要是为了计算方便，如果是double类型需要考虑两个点一样，斜率不存在的判断比int要复杂一些。
PointCollect类代表对点集可能存在的索引操作，找到点集的在一条直线的三元组只是他的一个功能之一，所以通过IFindLineHelper接口聚合到这个PointCollect类中。详细见UML，里面有两个函数，一个是O（N3）实现，一个是IFindLineHelper提供的，经过测试三者一致。
FindLineHelper和PointCollect都在实际计算过程都使用了PointFactory的接口，所以在UML图使用关联，trIp是一样的为了避免图复杂，就没有画，可以参考类的依赖关系图。
相关代码：
Program代码
class Program { static void Main(string[] args) { PointCollect pc = new PointCollect(); pc.PintPointInLine(); pc.ThreeCycleForPointInLine(); } }
PointFactory代码
public static class PointFactory { public static int PointCount { get { return DATACOUNT; } } static readonly int DATACOUNT=1000; /// <summary> /// 第二个维度中0存储坐标X的值， /// </summary> static readonly int X = 0; /// <summary> /// 第二个维度中1存储坐标Y的值 /// </summary> static readonly int Y = 1; /// <summary> /// 第二维度的长度 /// </summary> static readonly int D2 = 2; static int[,] pointArray; static PointFactory() { Random r = new Random(); int dataCount = DATACOUNT; pointArray = new int[dataCount, D2]; for (int i = 0; i < dataCount; i++) { pointArray[i,X] = r.Next(-dataCount, dataCount); pointArray[i,Y]= r.Next(-dataCount, dataCount); } } public static bool GetPointXY(int index,ref int x,ref int y) { if (index < DATACOUNT) { x = pointArray[index,X]; y = pointArray[index,Y]; return true; } else return false; } }
IFindLineHelper和PointCollect相关代码
public interface IFindLineHelper { /// <summary> ///在point集合中 /// 第start个至最后一个点所有的在一条直线的三元组 /// </summary> /// <param name="start"></param> /// <param name="mainIndex"></param> /// <returns></returns> List<Trip> GetTripTuple(int start, int mainIndex); } public class FindLineHelper : IFindLineHelper { private const double ERROR = 1.0e-10; private int[] indexArr; private double[] slopeArr; /// <summary> /// 指向indexArr和slopeArr 最后一个有效数据 /// 有效数据的长度Length=arrSp+1； /// </summary> private int arrSp; public FindLineHelper() { indexArr =new int[PointFactory.PointCount]; slopeArr=new double[PointFactory.PointCount]; arrSp = -1; } public List<Trip> GetTripTuple(int start, int mainIndex) { arrSp = -1; Build_I_S_Arr(start,mainIndex); QuickSortArr(0,arrSp); int i,j,k; i = mainIndex; List<Trip> listTrip = new List<Trip>(); for(j=0;j<arrSp;j++ ) { k=j+1; while(k<=arrSp &&Math.Abs(slopeArr[j]-slopeArr[k])<ERROR) { listTrip.Add( new Trip ( mainIndex,indexArr[j],indexArr[k]) ); k++; } } return listTrip; } /// <summary> /// 表示对indexArr和slopeArr进行赋值运算, /// </summary> /// <param name="start"></param> /// <param name="mainIndex"></param> private void Build_I_S_Arr(int start, int mainIndex) { int pa = mainIndex; int pax=0, pay=0; bool pointExist = false; pointExist = PointFactory.GetPointXY(pa, ref pax, ref pay); if (!pointExist) { Console.WriteLine("取数据出错，请注意Build_I_S_Arr函数"); return; } int pb=start; int pbx=0,pby=0; while (PointFactory.GetPointXY(pb, ref pbx, ref pby)) { if (pax == pbx && pay == pby) { Console.WriteLine("出现相同点，会影响数据"); } else if (pax == pbx) { //出现斜率不存在的点 arrSp++; indexArr[arrSp] = pb; slopeArr[arrSp] = double.MaxValue; } else { arrSp++; indexArr[arrSp] = pb; slopeArr[arrSp] = ((double)pay - pby) / (pax - pbx); } pb++; } } /// <summary> /// 对slopeArr进行快速排序，排序的同时需要对indexArr进行相应的操作 /// 保证索引信息与斜率一一对应。 /// </summary> /// <param name="begin"></param> /// <param name="end"></param> private void QuickSortArr(int begin,int end) { if (begin < end) { int keyIndex=indexArr[begin]; double keySlope = slopeArr[begin]; int i = begin, j = end; while (i < j) { while (i < j) { if (slopeArr[j] > keySlope) j--; else if (slopeArr[j] == keySlope && indexArr[j] >= keyIndex) { j--; } else break; } if (i < j) { indexArr[i] = indexArr[j]; slopeArr[i] = slopeArr[j]; } while (i < j) { if (slopeArr[i] < keySlope) i++; else if (slopeArr[i] == keySlope && indexArr[i] <= keyIndex) { i++; } else { break; } } if (i < j) { indexArr[j] = indexArr[i]; slopeArr[j] = slopeArr[i]; } } indexArr[i] = keyIndex; slopeArr[i] = keySlope; QuickSortArr(begin,i-1); QuickSortArr(i + 1, end); } } } public class PointCollect { IFindLineHelper _findLineHelper; int pointCount; public PointCollect() { _findLineHelper=new FindLineHelper(); pointCount=PointFactory.PointCount; } public void PintPointInLine() { int i=0,count=0; for(i=1;i<pointCount-2;i++) { List<Trip> listTrip=_findLineHelper.GetTripTuple(i,i-1); foreach(Trip tp in listTrip) { tp.print(); count++; } } Console.WriteLine(count); Console.ReadKey(); } public void ThreeCycleForPointInLine() { int count=0; for (int i = 0; i < pointCount - 2; i++) for (int j = i + 1; j < pointCount - 1; j++) for (int k = j + 1; k < pointCount; k++) { int xi=0,yi=0,xj=0,yj=0,xk=0,yk=0; PointFactory.GetPointXY(i,ref xi,ref yi); PointFactory.GetPointXY(j,ref xj,ref yj); PointFactory.GetPointXY(k,ref xk,ref yk); int Xij = xi-xj; int Yij = yi-yj; int Xjk = xk-xj; int Yjk = yk-yj; if ((Xij * Yjk - Yij * Xjk) == 0) { count++; Console.WriteLine("({0},{1},{2})", i, j, k); } } Console.WriteLine(count); Console.ReadKey(); } } public struct Trip { public int i, j, k; public Trip(int x, int y, int z) { i = x; j = y; k = z; } public void print() { Console.WriteLine("({0},{1},{2})", i, j, k); } }