文档章节

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

一贱书生
 一贱书生
发布于 2016/11/19 13:46
字数 520
阅读 8
收藏 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
04/08
0
0
台湾大学林轩田机器学习基石课程学习笔记5 -- Training versus Testing

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

红色de石头
2017/07/11
0
0
SVM学习笔记-线性支撑向量机

写在前面 本系列为学习林轩田老师讲解的SVM的笔记整理,共四篇,此为第一篇: SVM学习笔记-线性支撑向量机 SVM学习笔记-对偶形式的SVM SVM学习笔记-核函数与非线性SVM SVM学习笔记-软间隔SVM...

robin_Xu_shuai
2017/08/12
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

没有更多内容

加载失败,请刷新页面

加载更多

linux使用ntfs-3g操作ntfs格式硬盘

Linux内核目前只支持对微软NTFS文件系统的读取。 NTFS-3G 是微软 NTFS 文件系统的一个开源实现,同时支持读和写。NTFS-3G 开发者使用 FUSE 文件系统来辅助开发,同时对可移植性有益。 安装 ...

linuxprobe16
今天
1
0
kubeadm部署kubernetes集群

一、环境要求 这里使用RHEL7.5 master、etcd:192.168.10.101,主机名:master node1:192.168.10.103,主机名:node1 node2:192.168.10.104,主机名:node2 所有机子能基于主机名通信,编辑...

人在艹木中
今天
7
0
Shell特殊符号总结以及cut,sort,wc,uniq,tee,tr,split命令

特殊符号总结一 * 任意个任意字符 ? 任意一个字符 # 注释字符 \ 脱义字符 | 管道符 # #号后的备注被忽略[root@centos01 ~]# ls a.txt # 备注 a.txt[root@centos01 ~]# a=1[root@centos01...

野雪球
今天
2
0
OSChina 周二乱弹 —— 程序员圣衣

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @达尔文:分享Skeeter Davis的单曲《The End of the World》 《The End of the World》- Skeeter Davis 手机党少年们想听歌,请使劲儿戳(这里...

小小编辑
今天
18
0
[ python import module ] 导入模块

import moudle_name ----> import module_name.py ---> import module_name.py文件路径 -----> sys.path (这里进行查找文件) # from app.web import Personimport app.web.Person as Pe......

_______-
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部