文档章节

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

一贱书生
 一贱书生
发布于 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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Spring详解

Spring详解(一)------概述 目录 1、什么是 Spring ? 2、Spring 起源 3、Spring 特点 4、Spring 框架结构 5、Spring 框架特征 6、Spring 优点   本系列教程我们将对 Spring 进行详解的介绍...

DemonsI
13分钟前
0
0
CentOS7系统Nginx安装

1、下载nginx,官方网站https://nginx.org wget https://nginx.org/download/nginx-1.14.0.tar.gz 2、下载Nginx Sticky Module,官方网站https://bitbucket.org/nginx-goodies/nginx-sticky-......

m_lm
16分钟前
0
0
使用zTree树控件(二)

1:treeNode.checked用于判断是勾选还是取消勾选。(treeNode指的是节点)

uug
17分钟前
0
0
export, import 和 export default的区别

ES6的两个功能: export 和 import export 对外输出模块 import 引入(加载)进来一个模块 一、export => import 单个变量 export var name = "lishi" 在其他文件里引用 import {name} f...

Js_Mei
21分钟前
1
0
打造RecyclerView的n级列表

先上效果图: 1.该多级列表的优势: 支持无限级列表展开 基于一个recyclerView实现 可以自定义每一级item的样式,定制化更强 2.设计的思路 数据结构List<ItemBean>,ItemBean类中有变量List<...

WelliJohn
30分钟前
1
1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部