文档章节

在二维平面上,有一些点,请找出经过点数最多的那条线。

一贱书生
 一贱书生
发布于 2016/11/19 13:46
字数 520
阅读 25
收藏 0

/**

 * 功能:在二维平面上,有一些点,请找出经过点数最多的那条线。[java] view plain copy

 

  1. /** 
  2.      * 思路:在任意两点之间画一条无线长的直线,用散列表追踪那条直线出现的次数最多。时间复杂度O(N*N) 
  3.      * 注意: 
  4.      *      1)用斜率和y轴截距来确定是否是同一条直线。 
  5.      *      2)浮点数不一定能用二进制数准确表示,因此检查两个浮点数的差值是否在某个极小值(epsilon)内。 
  6.      *      3)对于散列表而言,斜率相等,未必散列值相同。因此,将斜率减去一个极小值,并以得到的结果flooredSlope作为散列键。 
  7.      *      4)取得所有可能相等的直线,搜索三个位置:flooredSlope,flooredSlope-epsilon,flooredSlope+epsilon。 
  8.      * @param points 
  9.      * @return 
  10.      */  
  11.     public static MyLine1 findBestLine(GraphPoint[] points){  
  12.         MyLine1 bestLine=null;  
  13.         int bestCount=0;  
  14.           
  15.         HashMap<Double,ArrayList<MyLine1>> lineBySlope=new HashMap<Double, ArrayList<MyLine1>>();  
  16.           
  17.         for(int i=0;i<points.length-1;i++){  
  18.             for(int j=i+1;j<points.length;j++){  
  19.                 MyLine1 line=new MyLine1(points[i],points[j]);  
  20.                 insertLine(lineBySlope,line);  
  21.                 int count=countEquivalentLines(lineBySlope,line);  
  22.                 if(count>bestCount){  
  23.                     bestCount=count;  
  24.                     bestLine=line;  
  25.                 }  
  26.             }  
  27.         }  
  28.         return bestLine;  
  29.           
  30.     }  
  31.   
  32.     private static int countEquivalentLines(HashMap<Double, ArrayList<MyLine1>> lineBySlope, MyLine1 line) {  
  33.         double key=line.floorToNearestEpsilon(line.slope);  
  34.         double eps=line.epsilon;  
  35.         int count=countEquivalentLines(lineBySlope.get(key), line)+countEquivalentLines(lineBySlope.get(key-eps), line)+  
  36.                 countEquivalentLines(lineBySlope.get(key+eps), line);  
  37.           
  38.         return count;  
  39.     }  
  40.       
  41.     public static int countEquivalentLines(ArrayList<MyLine1> lines,MyLine1 line){  
  42.         if(lines==null)  
  43.             return 0;  
  44.         int count=0;  
  45.         for(MyLine1 paralleLine:lines){  
  46.             if(paralleLine==line)  
  47.                 count++;  
  48.         }  
  49.         return count;  
  50.     }  
  51.   
  52.     private static void insertLine(HashMap<Double, ArrayList<MyLine1>> lineBySlope, MyLine1 line) {  
  53.         ArrayList<MyLine1> lines=null;  
  54.         double key=line.floorToNearestEpsilon(line.slope);  
  55.         if(!lineBySlope.containsKey(key)){  
  56.             lines=new ArrayList<MyLine1>();  
  57.             lineBySlope.put(key, lines);  
  58.         }else{  
  59.             lines=lineBySlope.get(key);  
  60.         }  
  61.         lines.add(line);//注意此处添加的用法  
  62.     }  
  63.       
  64.       
  65.   
  66. class MyLine1{  
  67.     public static double epsilon=0.0001;  
  68.     public double slope,intercept;  
  69.     public boolean infiniteSlope=false;  
  70.       
  71.     public MyLine1(GraphPoint p,GraphPoint q){  
  72.         if(Math.abs(p.x-q.x)>epsilon){//两个点的x坐标不同  
  73.             slope=(p.y-q.y)/(p.x-q.x);//斜率  
  74.             intercept=p.y-slope*p.x;//y轴截距  
  75.         }else{  
  76.             infiniteSlope=true;  
  77.             intercept=p.x;//x轴截距  
  78.         }  
  79.     }  
  80.       
  81.     public double floorToNearestEpsilon(double d){  
  82.         int r=(int) (d/epsilon);//使原d保留小数位后的4位(epsilon=0.0001)  
  83.         return ((double)r)*epsilon;  
  84.     }  
  85.       
  86.     public boolean isEquivalent(MyLine1 line){  
  87.         if((slope==line.slope)&&(intercept==line.intercept)&&(infiniteSlope==line.infiniteSlope))  
  88.             return true;  
  89.         return false;  
  90.     }  
  91.       
  92.     public boolean isEquivalent(double a,double b){  
  93.         return Math.abs(a-b)<epsilon;  
  94.     }  
  95.       
  96.   
  97.       
  98. }  
  99.   
  100. class GraphPoint{  
  101.     int x;  
  102.     int y;  
  103.       
  104.     public GraphPoint(int x,int y){  
  105.         this.x=x;  
  106.         this.y=y;  
  107.     }  

 

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
CF EDU 41 D 题 Pair Of Lines 【经典几何题】

传送门 题意: 给定n个二维平面上的点, 问这些点是否存在于两条直线上.. (如果还对题意比较迷, 那就再说一种那就是所有点共线时也是YES) 思路: 首先, 如果点数<3, 很明显是YES, 所以当点数大于...

anxdada
2018/04/08
0
0
[转]随机采样一致性(RANSAC)

作者:桂。 时间:2017-04-25 21:05:07 链接:http://www.cnblogs.com/xingshansi/p/6763668.html 前言 仍然是昨天的问题,别人问到最小二乘、霍夫变换、RANSAC在直线拟合上的区别。昨天梳理...

lege675797663
2018/04/10
0
0
台湾大学林轩田机器学习基石课程学习笔记5 -- Training versus Testing

上节课,我们主要介绍了机器学习的可行性。首先,由NFL定理可知,机器学习貌似是不可行的。但是,随后引入了统计学知识,如果样本数据足够大,且hypothesis个数有限,那么机器学习一般就是可...

红色de石头
2017/07/11
0
0
在二维平面上,有两个正方形,请找出一条直线,能够将这两个正方形对半分

/** * 功能:在二维平面上,有两个正方形,请找出一条直线,能够将这两个正方形对半分。 * 假定正方形的上下两条边与x轴平行。 / [java] view plain copy /* * 考虑: * 线的准确含义,可能性...

一贱书生
2016/11/19
21
0
leetcode 149. Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. 题意:给一个二维平面,上面有好多点,有横纵坐标,找出一条直线,使得这条线上的点...

努力的C
2017/10/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Navicat怎样导入Excel表格和txt文本的数据

Navicat怎样导入Excel表格和txt文本的数据 2018年07月02日 11:29:11 零碎de記憶 阅读数:2433 版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/qq_39135287/ar...

linjin200
31分钟前
1
0
使用MaxCompute Java SDK运行安全相关命令

使用MaxCompute Console的同学,可能都使用过MaxCompute安全相关的命令。官方文档上有详细的MaxCompute 安全指南 ,并给出了安全相关语句汇总 。 简而言之, 权限管理 、 列级别访问控制 、 ...

阿里云云栖社区
36分钟前
0
0
中小公司的Java工程师应该如何逆袭冲进BAT?

(1)80% Java工程师都有的迷茫 这篇文章,跟大家聊一聊很多很多很多人问我的一个问题:中小公司的Java工程师应该如何规划准备,才能跳槽进入BAT这类一线互联网公司? 之所以我用了三个 “很...

Java填坑路
37分钟前
4
0
你的应用够安全吗?绿标2.0隐私权限详解

近日,最新一期的《绿色应用达标率调查报告》结果显示,应用在安全方面的通过率仅为57%,相较于其他四项标准通过率最低。其中隐私权限的过度获取是主要原因之一,需要开发者尽快完成整改。 ...

安卓绿色联盟
47分钟前
1
0
使用MaxCompute Java SDK运行安全相关命令

使用MaxCompute Console的同学,可能都使用过MaxCompute安全相关的命令。官方文档上有详细的MaxCompute安全指南,并给出了安全相关语句汇总。 简而言之,权限管理、列级别访问控制、项目空间...

阿里云官方博客
52分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部