Max Points on a Line ！！！！！！！！！！！！！！！！！！

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

A:
现在的思路，就是，先根据slope 分组，  具有相同(很接近）斜率 slope的点放到一组。
然后，对每一组， 再找出具有相同(很接近） 的截距（intersect）的点来。 --记录最大的list的长度，然后返回即可。--------------理论上来讲，是O(n^2)
注意： 重复的点，也算不同的点来count
哎，就TM知道， 不能用这种屌丝办法，会超时，  现在好了，真的超时了。废了一晚上的时间。~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~主要的时间开销，就在Step1 里的双重循环上了。（对每个点，找它的所有的slope），其目的是： 将具有same  slope 的组合 放到一起。（虽然，可能不是相同的节点）
-----------------------------------------代码见本页最后--------------------------------



----------------其实，不是算法复杂度的问题， 是利用了O(n^2)的空间的问题。  也存储了太多的，冗余的slope。------------------------

--------------------------下面是别人的思路-------------------------------------------------
分析：首先要注意的是，输入数组中可能有重复的点。由于两点确定一条直线，一个很直观的解法是计算每两个点形成的直线，然后把相同的直线合并，最后 包含点最多的直线上点的个数就是本题的解。我们知道表示一条直线可以用斜率和y截距两个浮点数（垂直于x轴的直线斜率为无穷大，截距用x截距），同时还需 要保存每条直线上的点（避免重复）。听起来就很麻烦，但是基于这个思想有一种简单的实现方式：

• 以某点O为中心，计算它和其他点的斜率，如果有两个点A、B和O点形成的斜率相等，那么ABO三点是共线的，如果有多个点和O的斜率相等，那么这 多个点和O也是共线的，因此我们可以求出包含O的所有直线中点数最多的直线，会得到一个最大共线点数k(O)，如果和O点重复的点有n个（除了O本身）， 那么K(O) = K(O) + n。这一步的计算中，为了提高效率，我们可以用哈希表来保存某个斜率对应的点的数目。
• 对数组中的每一个点i，按照第一步计算得到每个点最大点数K(i)
• 从k(i)中选取最大的就是本题的解
• 注意：为了避免重复计算，以数组中第i个点为中心时，只计算数组中它右边的所有点        

public class MaxPointsOnALine2 {

    public int maxPoints(Point[] points) {
        // for each point, we calculate its slope with others,
        // if they are the same, we save them into a Hashtable
        if (points.length <= 1) { // pay attention to length == 1
            return points.length;
        }
        int nMaxPoints = 0;

        for (int i = 0; i < points.length - 1; i++) {
            // for slope Double, we map its count of integers that could form
            // this slope with points[i]

            Map<Long, Integer> map = new HashMap<Long, Integer>();
            Point pLeft = points[i];
            int nDuplicate = 1; // how many points that having the same (x,y)
                                // value with pLeft(inclusive)
            for (int j = i + 1; j < points.length; j++) {
                Point pRight = points[j];
                if (pLeft.x == pRight.x && pLeft.y == pRight.y) {
                    nDuplicate++;
                    continue;
                } else {
                    Long longSlope;  // is is 10000* actuall slope
                    // calculate their slope and save into a the HashMap
                    if (pLeft.x == pRight.x) {
                        longSlope = Long.MAX_VALUE;
                    } else {
                        double slope = (double) (pRight.y - pLeft.y) / (pRight.x - pLeft.x);
//                        slope = BigDecimal.valueOf(slope).setScale(5, BigDecimal.ROUND_HALF_DOWN)
//                                .doubleValue();// round the slope
                        longSlope =Math.round(slope*10000);
                    }
                    // insert the slope into the hashMap
                    Integer objCount = map.get(longSlope);
                    if (objCount == null) {
                        map.put(longSlope, 1);
                    } else {
                        map.put(longSlope, objCount + 1);
                    }
                }
            }// enf of for loop ---- j
            nMaxPoints = Math.max(nMaxPoints, nDuplicate); // in case that
                                                            // HashMap is empty
            // search all slopes passing pLeft, and update the nMaxPoints
            Iterator<Entry<Long, Integer>> iter = map.entrySet().iterator();
            while (iter.hasNext()) { // for each slope, need find the max point
                Map.Entry<Long, Integer> entry = (Map.Entry<Long, Integer>) iter.next();
                Integer curCount = (Integer) entry.getValue();
                nMaxPoints = Math.max(nMaxPoints, curCount + nDuplicate);
            } // end of while
        } // end of for loop ----- ivalue

        return nMaxPoints;
    }
}

罪魁祸首找到啦~~~~~~~~~~~~~~， 就是
//                        slope = BigDecimal.valueOf(slope).setScale(5, BigDecimal.ROUND_HALF_DOWN)
//                                .doubleValue();// round the slope
把这句话注释掉，就可以了。  ~~~~~~~加上这句话，  运行时间，变成了10倍多。
~~~~~~~~可是，不是说double不能完全一样的值吗？？？？？？？？？？？
嗯，出现问题了，  去掉这句话之后， 出现  -0.0 和0.0 的slope不一样的问题。怎么办？？？？

解决方法就是： 把double的slope * 10000, 转换成long 类型，就行了。

因此，方法一，也如此解决pass。    具体修改，可以见Eclipse中的代码。  （而且，上面的代码，也没有处理duplicates 的问题。  因此，还是只看解法2吧。


Mistakes:
1：  刚开始，没有考虑，输入数组的长度为0， 为1 的情况。  反而在题目中，直接默认为长度超过2了。  直接调用了， slopeList[0] 啊什么的

2:： 对于slope 为正无穷的情况， 在求 difference  of intersect的时候，要要单独处理，  其各自的intersect 可以用point.x 的值代替。

 3： 注意： 重复的点，也算不同的点来count。  但是，在实际

4： 一开始，设
        double minDiff = 0.0000001;
结果太小了，计算机的round error还是超过了这个值。 更改为
        double minDiff = 0.00001;  

5: 方法二的时候， update nMaxPoints 在第二个for循环后面，而且，刚开始，弄成iter 必须是非空才能update 的。因此，对于输入  ”(0,0)，(0,0)“  就不能update nMaxPoints了。


Learned:
1:  round  a double data,   可以用下面的代码：
        double slope = 2.1234567;
        slope = BigDecimal.valueOf(slope).setScale(5, BigDecimal.ROUND_HALF_UP).doubleValue();
        System.out.println(slope);
打印的结果是   2.12346
2：  在leetcode中，也可以在class的前面，加入import 语句。

3： 如何遍历一个HashMap
Map map = new HashMap();
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
    Map.Entry entry = (Map.Entry) iter.next();
    Object key = entry.getKey();
    Object val = entry.getValue();
}
效率高,以后一定要使用此种方式！
3.5------------------另一种方式，更简单 ----------------
HashMap<Integer,Integer> map = new HashSet<Integer,Integer>();
for(int key : map.keySet()
        // do something

4：  表示直线，

First, DO NOT use double in such kind of problem, you don't need them and they will make you suffer, DO use integers
Second, <k, b> is not a good idea simply because you cannot represent all the possible line using it.
You can use <a, b, c> to represent all the possible line, i.e., ax + by + c = 0 where a, b, c are all integers.

--------------------------------------------第二遍-----------------------------------------

没有去遍历map，而直接是在建立的时候，查询并保存了结果。


Big Mistake: 
        当计算斜率的时候，  long / long  的结果是 long 的， 而不是double的， 因此，要想 得到小数的结果， 需要把一个先转换成double类型，  我艹~~~~~~~~~~~~~~~~~~~  你SB，~~~~~脑子坏掉了。 Tiger

import java.util.*;

public class Solution {
    public int maxPoints(Point[] points) {
        if (points.length <= 1)
            return points.length;
        int maxPointOnLine = 0;
        HashMap<Long, Integer> map = new HashMap<Long, Integer>();// map scale to count
        for (int i = 0; i < points.length; i++) {
            map.clear();
            int duplicate = 1;
            int maxCount = 0;
            for (int j = i + 1; j < points.length; j++) {
                Long ratio = 0L;
                if (points[j].x == points[i].x && points[j].y == points[i].y) {
                    duplicate++;
                } else {
                    if (points[j].x == points[i].x)
                        ratio = Long.MAX_VALUE;
                    else
                        ratio = (long) ( (double)(points[j].y - points[i].y) / (points[j].x - points[i].x) * 100000);
                    int count  =1;
                    if (map.get(ratio) != null)
                        count = map.get(ratio) +1;
                    map.put(ratio, count);
                    maxCount = Math.max(maxCount, count);
                }
            }
            maxPointOnLine = Math.max(maxPointOnLine, duplicate + maxCount);
        }
        return maxPointOnLine;
    }
}

错误2 ：     2遍都有这个错误。 
另外，  在update maxPointOnLine 的时候， 不能把              maxPointOnLine 放到for  ( int   j) 这个循环的里边， 会导致  update的时候，  count 和 nDuplicate 不同时是最大的。  因此，要放到外边去。里层循环， 记录斜率的maxCount  .

哎，Tiger，先不要节省代码行数， 即使超出30行又能如何？ 要保证正确才对。

错误3： 
曾经写过这样   count  = （map.get(key) == null)? 0 : map.get(key)   + 1 ;  这样的结果不是预期的。   不知道为什么  ~~~~~~~~





--------------------------------解法1 的代码（没pass，只代表思路）----------------------

import java.math.BigDecimal;
import java.util.Map;
import java.util.Map.Entry;

public class Solution {
public int maxPoints(Point[] points) {
        // first divided by slope,
        // NOTE: due to the fact that digital numbers cannot be too concise, we
        // use approximatin
        if (points == null || points.length == 0)
            return 0;
        if (points.length == 1)
            return 1;
        double minDiff = 0.00001;
        Map<Double, Integer> map = new HashMap<Double, Integer>();
        // a map from slope into the position of List of Points
        ArrayList<HashSet<Point>> slopeList = new ArrayList<HashSet<Point>>();

        // Step1: for each pair of points, calculte their slope and add them
        // into the hashMap
        for (int i = 0; i < points.length - 1; i++) {
            for (int j = i + 1; j < points.length; j++) {
                Point pLeft = points[i].x < points[j].x ? points[i] : points[j];
                Point pRight = points[i].x >= points[j].x ? points[i] : points[j];
                double slope;
                if (pRight.x - pLeft.x == 0) {
                    slope = Double.MAX_VALUE;
                } else {
                    slope =( (double)(pRight.y - pLeft.y)) / (pRight.x - pLeft.x);
                    slope = BigDecimal.valueOf(slope).setScale(5, BigDecimal.ROUND_HALF_DOWN)
                            .doubleValue();// round the slope
                }
                Integer index = map.get(slope);
                if (index == null) { // if current slope is not found
                    index = slopeList.size();
                    map.put(slope, slopeList.size()); // add at last position
                    HashSet<Point> tmp = new HashSet<Point>();
                    slopeList.add(tmp); // add one element at slopeList
                }
                HashSet<Point> tmpSet = slopeList.get(index);
                tmpSet.add(pLeft);
                tmpSet.add(pRight);
            }
        }

        // Step 2: now all list contains points of same slope, with some of
        // its neighgbors,
        // we try to find , if using same slope, check the intersect difference
        int maxPoints = 0;
        Iterator<Entry<Double, Integer>> iter = map.entrySet().iterator();
        while (iter.hasNext()) { // for each slope, need find the max point
                                    // through a line ,coz they might parrelel
            Map.Entry<Double, Integer> entry = (Map.Entry<Double, Integer>) iter.next();
            Double slope = (Double) entry.getKey();
            Integer index = (Integer) entry.getValue();

            HashSet<Point> curSet = slopeList.get(index);
            if (curSet.size() <= maxPoints) {
                continue;
            }
            // each element contains lists that having same slope and intersect 
            ArrayList<ArrayList<Point>> all = new ArrayList<ArrayList<Point>>();
            for (Point eachPoint : curSet) { // check the difference with
                                                // existing ones
                boolean findGroup = false;
                // check all points in the list, that might belongs to same
                // group
                for (int j = 0; j < all.size(); j++) {
                    // if found the node that with intercept small enough
                    // arraylist, with same slope and same intersect
                    ArrayList<Point> al = all.get(j);
                    double curIntercept, newIntersect;
                    if (slope == Double.MAX_VALUE) {
                        curIntercept = al.get(0).x;
                        newIntersect = eachPoint.x;
                    } else {
                        curIntercept = al.get(0).y - slope * al.get(0).x;
                        newIntersect = eachPoint.y - slope * eachPoint.x;
                    }
                    if (Math.abs(curIntercept - newIntersect) < minDiff) {
                        al.add(eachPoint);
                        findGroup = true;
                        break;
                    }
                }
                // if not find its group, we append this point to all
                if (findGroup == false) {
                    ArrayList<Point> al = new ArrayList<Point>();
                    al.add(eachPoint);
                    all.add(al);
                }
            }
            // find the maximun number of List, for current slope,
            for (int i = 0; i < all.size(); i++) {
                ArrayList<Point> al = all.get(i);
                if (al.size() > maxPoints) {
                    maxPoints = al.size();
                }
            }
        }
        return maxPoints;
    }
}