题目：
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
此题就是要考虑所有的情况：
需要两重循环，第一重循环遍历起始点a，第二重循环遍历剩余点b。
a和b如果不重合，就可以确定一条直线。
对于每个点a，构建 斜率->点数 的map。
(1)b与a重合，以a起始的所有直线点数+1 (用dup统一相加)
(2)b与a不重合，a与b确定的直线点数+1
代码：
package chap8; import java.util.HashMap; import java.util.Map; /** * Given n points on a 2D plane, find the * maximum number of points that lie on the same straight line. * @author wwq * */ class Point { int x; int y; Point() { x = 0; y = 0; } Point(int a, int b) { x = a; y = b; } } public class maxPoints { public static int maxPoints(Point[] points) { int n = points.length; if(n < 2) return n; int ret = 0; for(int i = 0; i < n; i++) { // 分别统计与点i重合以及垂直的点的个数 int dup = 1, vtl = 0; Map<Float, Integer> map = new HashMap<>(); Point a = points[i]; for(int j = 0; j < n; j++) { if(i == j) continue; Point b = points[j]; if(a.x == b.x) { if(a.y == b.y) dup++;//记录重合的数目 else vtl++;//记录垂直的数目 //当不重合也不垂直的时候，就可以计算斜率了，斜率相等则在一条直线上，加1; } else { float k = (float)(a.y - b.y) / (a.x - b.x); if(map.get(k) == null) map.put(k, 1); else map.put(k, map.get(k) + 1); } } //求出当前已a为起始节点的 ，最大的数目 int max = vtl; for(float k: map.keySet()) { max = Math.max(max, map.get(k)); } //保留上一次的最大节点数目 ret = Math.max(ret, max + dup); } return ret; } public static void main(String[] args) { // TODO Auto-generated method stub Point num=new Point(0,0); Point num2=new Point(1,1); Point num3=new Point(1,-1); Point[] arraynum= {num,num2,num3}; System.out.println(maxPoints(arraynum)); } }转载地址：https://www.nowcoder.com/profile/326932779/codeBookDetail?submissionId=43872812
