[算法]给定一个二维平面，平面有n个点，求最多有多少个点在同一条直线上

某人丢给我的算法题…
给定一个二维平面，平面有n个点，求最多有多少个点在同一条直线上

示例1:

输入：[[1,1],[2,2],[3,3]]
输出：3
解释：
^
|       o       
|    o          
| o             
+--------------->
0 1  2  3  4  5 

示例2:

输入：[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出:4
解释:
^
| o                
|    o        o    
|       o          
| o        o       
+------------------>
0 1  2  3  4  5  6 

## java代码实现

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class PointMapTest {

    public static void main(String[] args) {
        //int[][] t = new int[][]{{1,1},{2,2},{3,3}};
        int[][] t = new int[][]{{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}};

        /**
         * 运算有多少直线公式
         */
        Set<String> kset = new HashSet<>();
        for(int i=0;i<t.length-1;i++){
            for(int j=0;j<t.length-1-i;j++){
                String k = calKey(t[j], t[j+1]);
                kset.add(k);
            }
        }

        /**
         * 验证每个直线公式有多少点
         */
        Map<String,Integer> countMap = new HashMap<>();
        Iterator<String> it = kset.iterator();
        while(it.hasNext()){
            String k = it.next();
            int count = 0;
            for(int i = 0; i < t.length; i++){
                boolean flag = mat(t[i], k);
                if(flag) count ++;
            }
            countMap.put(k, count);
        }
        /**
         * 输出做大的一个公式有多少个点
         */
        List<Integer> l1 = new ArrayList<>(countMap.values());
        Integer max = Collections.max(l1);
        System.out.println("输出:" + max);
        System.out.println("解释:");

        /**
         * 计算地图大小
         */
        int maxX = 0;
        int maxY = 0;
        for(int i = 0 ;  i< t.length; i++){
            int tempX = t[i][0];
            int tempY = t[i][1];
            maxX = maxX > tempX ? max : tempX;
            maxY = maxY > tempY ? maxY : tempY;
        }

        /**
         * 生成初始化地图数组
         */
        String[][] map  = new String[maxX][maxY+2];
        for(int i = 0 ; i < map.length; i ++){
            for(int j = 0 ; j < map[0].length ; j++){
                try{
                    map[i][j] = "   ";
                }catch (Exception e) {
                    System.err.println("i:" + i+ ",j :" + j);
                }
            }
        }
        /**
         * 将坐标点转换到地图数组中
         * 1.上下反转
         * 2.逆时针旋转90度
         */
        for(int i = 0 ; i < t.length; i++){
            map[t[i][1] - 1][t[i][0] - 1] = " o ";
        }

        /**
         * 打印地图
         */
        String mapString = printMap(map);
        System.out.println(mapString);
    }

    /**
     * 计算两个点的公式
     * AX+BY+C=0
     * A = Y2 - Y1
     * B = X1 - X2
     * C = X2*Y1 - X1*Y2
     */
    public static String calKey(int[] a, int[] b){
        int y2 = b[1];
        int y1 = a[1];
        int x1 = a[0];
        int x2 = b[0];
        int aa = y2 - y1;
        int ba = x1 - x2;
        int c = x2 * y1 - x1 * y2;
        return aa + "_" +ba + "_" + c;
    }

    /**
     * 验证点是否在直线上
     * @param a 点
     * @param k 直线公式
     */
    public static boolean mat(int[]a, String k){
        String[] s = k.split("_");
        int x = Integer.parseInt(s[0]);
        int y = Integer.parseInt(s[1]);
        int c = Integer.parseInt(s[2]);
        return 0 == (x * a[0] + y * a[1] + c);
    }

    /**
     * 打印地图
     */
    public static String printMap(String[][] map){
        StringBuilder sb = new StringBuilder();
        sb.append("^");
        sb.append("\n");
        for(int i = 0 ; i < map.length; i ++){
            sb.append("|");
            for(int j = 0 ;j < map[0].length; j++){
                sb.append(map[map.length - i - 1][j]);
            }
            sb.append("\n");
        }
        sb.append("+");
        for(int i = 0 ; i < map[0].length; i++){
            sb.append("---");
        }
        sb.append(">").append("\n");

        sb.append("0");
        for(int i = 0 ; i < map[0].length; i++){
            sb.append(" "+(i+1)+" ");
        }
        sb.append("\n");
        return sb.toString();
    }

}

控制台打印结果

输出:4
解释:
^
| o                
|    o        o    
|       o          
| o        o       
+------------------>
0 1  2  3  4  5  6