首页 > 其他 > 详细

Max Points on a Line

时间:2014-02-25 02:58:56      阅读:417      评论:0      收藏:0      [点我收藏+]
bubuko.com,布布扣
 1 public class Solution {
 2     public int maxPoints(Point[] points) {
 3         HashMap<Double,Integer> map = new HashMap<Double,Integer>();
 4         int res = 0;
 5         for(int i=0;i<points.length;i++){
 6             map.clear();
 7             int curMax = 1;
 8             int sameP =0;
 9             for(int j=i+1;j<points.length;j++){
10                 double slop = Double.MAX_VALUE;
11                 if(points[i].x==points[j].x && points[j].y==points[i].y){
12                     sameP++;
13                     continue;
14                 }
15                 else if(points[j].y==points[i].y){
16                     slop =0.0;//y1==y2 because double has -0.0
17                 }
18                 else if(points[i].x!=points[j].x && points[j].y!=points[i].y){
19                     slop = (1.0*(points[i].y-points[j].y)/(points[i].x-points[j].x)); 
20                 }
21                 if(map.containsKey(slop)){
22                     int temp = map.get(slop);
23                     map.put(slop,temp+1);
24                     curMax = Math.max(curMax,temp+1);
25                 }
26                 else{
27                     map.put(slop,2);
28                     curMax = Math.max(curMax,2);
29                 }
30             }
31             res = Math.max(curMax+sameP,res);
32         }
33         return res;
34     }
35 }
View Code

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

Max Points on a Line

原文:http://www.cnblogs.com/krunning/p/3563990.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!