精华内容
下载资源
问答
  • 需求:给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上。 分析思路: 1、将所有点二维坐标化,即定义出所有点的x,y坐标值 2、遍历出所有取出两点的情况(不考虑先后顺序),根据任意两点都确定一...

    需求:给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上。

    分析思路:
    1、将所有点二维坐标化,即定义出所有点的x,y坐标值
    2、遍历出所有取出两点的情况(不考虑先后顺序),根据任意两点都确定一条直线,直线参数为k斜率,b与y轴交点的纵坐标(此时x=0),将他们放入一个列表中
    3、将所有直线放入一个集合并完成去重操作,增加直线的第三个参数n=0用于第四步判断每条直线上有几个点
    4、将所有点遍历并判断是否在集合中的直线上,若在直线上,则直线对应的n加1
    5、遍历所有代表直线的列表,取出n最大的直线其n值就是最多有n个点在此条直线上

    def line(point1, point2):     
    	#定义一个函数通过两点来计算出对应直线的参数,
    	#传入的参数point1、point2都是列表
    	try:
            y1 = point1[1]
            y2 = point2[1]
            x1 = point1[0]
            x2 = point2[0]
      	    #根据列表对应下标取出x、y值
            k = (y2-y1)/(x2-x1)
            #根据x、y值计算出斜率,当斜率无穷大时报错,进入except
            b = y1-k*x1
            #计算出b
            return [k, b,0]
            #返回直线参数,第三个参数为0,用来后面的计数
        except Exception:
            return ["+8", y1, 0]
            #当报错时意味着斜率为无穷大,我们用"+8"代替
    
    
    def judge_in(point_in, line_in):
    	#用来判断点是否在直线上,若在则返回True,
    	#若不在则返回False
        x_in = point_in[0]
        y_in = point_in[1]
        k_in = line_in[0]
        b_in = line_in[1]
        if k_in == "+8":
        #当斜率无穷大时,单独判断
            if b_in == y_in:
                return True
            else:
                return False
        elif y_in == x_in*k_in+b_in:
            return True
        else:
            return False
    
    """可以改变下方列表中点的参数"""
    point_list = [[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]]
    #给出一个包含几个点的列表
    
    
    # point_list = [[1,1],[2,2],[3,3]]
    line_list = []
    #新建一个用来接收直线的空列表
    new_list = []
    #直线去重后加入此列表
    for i in range(len(point_list)):
        for j in range(i+1, len(point_list)):
        #通过双层的for循环给出所有两个点的组合
            line_s = line(point_list[i], point_list[j])
            #利用函数求出直线的前两个参数
            line_list.append(line_s)
    
    print(line_list)
    #得到的是一组有重复参数的直线
    for k in line_list:
        if k not in new_list:
        #去重
            new_list.append(k)
    for m in point_list:
        for n in new_list:
        #遍历所有点和线,判断点是否在线上,
        #若在则直线第三个用来计数的参数加1
            if judge_in(m, n):
                n[2] += 1
    print(new_list)
    #输出去重完毕后的列表,再经过一次遍历即可找出最多点所在的直线
    
    展开全文
  • 题目:对于给定的n个位于同一二维平面上的点,求最多多少个点位于同一直线上 理解: 1.首先明白这道题的解题思路应该是进行穷举 2.其次是如何判断多个点都在一条直线上,那就是计算斜率,如果一个点和多个点计算...

    题目:对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上

    理解:

    1.首先明白这道题的解题思路应该是进行穷举
    2.其次是如何判断多个点都在一条直线上,那就是计算斜率,如果一个点和多个点计算的斜率都是相同的,那就意味着这几个点是在一条直线上的
    3.那么这道题的思路就已经出来了:通过两层的循环,针对每个点都与其他的点进行计算斜率,对计算结果相同的斜率进行计数,取出最大值。也就是说每个点都会取一个最大值,我们还要取出最大的值。

    细节(方法)把握:

    1.两层的循环肯定是用双层for循环来进行
    2.针对于斜率的计数方法,用hashmap就可以做到,<斜率,次数>,这也是我最开始对java不太熟悉的地方,hashmap不允许存储重复key,这就意味着我们如果每次添加相同的斜率(key)和不同次数,就会覆盖原来的,这样一来就很便捷
    3.再针对于两点计算斜率时可能出现的情况:
    第一种情况:两点重合,由于我们每次一个内层for循环都是针对于一个相同的点和所有其他的点进行计算,那么有可能会出现点重合的情况,那么这种情况其实也算共线。如果我们计算得出该点和n个不同的点共线,那么最后还要把重合的点数一起算上去
    第二种情况:斜率不存在,也就是两点在一个垂直水平线上,那么这时候就要单独进行计数了
    第三种情况:在一条水平线上,这种情况其实可以不做讨论,因为在同一水平线上就意味着斜率为零,是可以计算出来的!

    实现遇见的小问题:

    1.斜率是有正负的,我最开始竟然设置了绝对值,导致出错
    2.一开始就要考虑传入的参数数组是否为空,这也是样例输入,导致出现错误
    3.斜率是有可能为小数的,但是我们定义点的时候都是int,所以计算斜率之前都要把除数和被除数都转为double,int转double是可以直接隐式转换的!

    /**
     * Definition for a point.
     * class Point {
     *     int x;
     *     int y;
     *     Point() { x = 0; y = 0; }
     *     Point(int a, int b) { x = a; y = b; }
     * }
     */
    import java.util.HashMap;
    import java.util.Iterator;
    import java.util.Map;
    public class Solution {
        public int maxPoints(Point[] points) {
            if(points.length == 0) return 0;
            int result = 0;//最终结果
            for(int i =0 ; i < points.length; i++){
                HashMap<Double,Integer> hashMap = new HashMap<>();
                int coincide = 0;//记录重合点数
                int vertical = 0;//记录斜率不存在的点数
                int horizon = 0;//记录水平点数 没有用到其实
                Integer max = 0;//记录每次从map中取到的最大值
                for(int j = 0; j < points.length; j++){
                    //同一个点不进行计算
                    if(i == j) continue;
                    //斜率有正负
                    double ydex = points[j].y-points[i].y;
                    double xdex = points[j].x-points[i].x;
    
                    if(ydex == 0 && xdex == 0){//两个点重合
                        coincide +=1;
    //                }else if(ydex == 0 && xdex != 0){//在一条水平线上
    //                    horizon +=1;
                    }else if(xdex == 0 && ydex != 0){//在一条垂直线上
                        vertical +=1;
                    }else {//斜率存在
                        Double k = (Double) ydex/xdex;
                        if(hashMap.containsKey(k)){
                            hashMap.put(k,hashMap.get(k)+1);
                        }else {
                            hashMap.put(k,1);
                        }
                    }
                }
                //遍历map寻找最大值
                Iterator iterable = hashMap.entrySet().iterator();
                while(iterable.hasNext()){
                    Map.Entry entry = (Map.Entry) iterable.next();
                    Integer sum = (Integer) entry.getValue();
                    if(sum > max)  max = sum;
                }
                max = Math.max(vertical,max); //和垂直线上的点数比较
    //            max = Math.max(horizon,max);
                max += coincide; //加上重合的点数
                
    
                if(max > result) result = max;
    
            }
            result += 1;  //这里是把自己也算进去
            return result;
        }
    }
    
    
    
    展开全文
  • 【初中数学】102条做初中几何辅导线的规律线、角、相交线、平行线 规律1 如果平面上有n(n≥... 规律3 如果一条直线上有n个点,那么在这个图形中共有线段的条数为n(n-1)条。 规律4 线段(或延长线)上任一点分线...

    672cdb058cecb281a8ade5375fb50463.png【初中数学】102条做初中几何辅导线的规律

    线、角、相交线、平行线

      规律1

      如果平面上有n(n≥2)个点,其中任何三点都不在同一直线上,那么每两点画一条直线,一共可以画出n(n1)条。

      规律2

      平面上的n条直线最多可把平面分成〔n(n+1)+1〕个部分。

      规律3

      如果一条直线上有n个点,那么在这个图形中共有线段的条数为n(n1)条。

      规律4

      线段(或延长线)上任一点分线段为两段,这两条线段的中点的距离等于线段长的一半。

      规律5

      有公共端点的n条射线所构成的交点的个数一共有n(n1)个。

      规律6

      如果平面内有n条直线都经过同一点,则可构成小于平角的角共有2n(n1)个。

      规律7

      如果平面内有n条直线都经过同一点,则可构成n(n1)对对顶角。

      规律8

      平面上若有n(n≥3)个点,任意三个点不在同一直线上,过任意三点作三角形一共可作出n(n1)(n2)个。

      规律9

      互为邻补角的两个角平分线所成的角的度数为90°

      规律10

      平面上有n条直线相交,最多交点的个数为n(n1)个。

      规律11

      互为补角中较小角的余角等于这两个互为补角的角的差的一半。

      规律12

      当两直线平行时,同位角的角平分线互相平行,内错角的角平分线互相平行,同旁内角的角平分线互相垂直。

    规律13

      已知ABDE,如图⑴~⑹,规律如下:

      规律14

      成“8”字形的两个三角形的一对内角平分线相交所成的角等于另两个内角和的一半。

    三角形部分

      规律15

      在利用三角形三边关系证明线段不等关系时,如果直接证不出来,可连结两点或延长某边构造三角形,使结论中出现的线段在一个或几个三角形中,再利用三边关系定理及不等式性质证题。

      注意:利用三角形三边关系定理及推论证题时,常通过引辅助线,把求证的量(或与求证有关的量)移到同一个或几个三角形中去然后再证题。

      规律16

      三角形的一个内角平分线与一个外角平分线相交所成的锐角,等于第三个内角的一半。

      规律17

      三角形的两个内角平分线相交所成的钝角等于90o加上第三个内角的一半。

    规律18

      三角形的两个外角平分线相交所成的锐角等于90o减去第三个内角的一半。

      规律19

      从三角形的一个顶点作高线和角平分线,它们所夹的角等于三角形另外两个角差(的绝对值)的一半。

      注意:同学们在学习几何时,可以把自己证完的题进行适当变换,从而使自己通过解一道题掌握一类题,提高自己举一反三、灵活应变的能力。

      规律20

      在利用三角形的外角大于任何和它不相邻的内角证明角的不等关系时,如果直接证不出来,可连结两点或延长某边,构造三角形,使求证的大角在某个三角形外角的位置上,小角处在内角的位置上,再利用外角定理证题。

      规律21

      有角平分线时常在角两边截取相等的线段,构造全等三角形。

      规律22

      有以线段中点为端点的线段时,常加倍延长此线段构造全等三角形。

      规律23

      在三角形中有中线时,常加倍延长中线构造全等三角形。

      规律24

      截长补短作辅助线的方法

      截长法:在较长的线段上截取一条线段等于较短线段;

      补短法:延长较短线段和较长线段相等.

      这两种方法统称截长补短法。

      当已知或求证中涉及到线段abcd有下列情况之一时用此种方法:

    ab

    a±b= c

    a±b= c±d

      规律25

      证明两条线段相等的步骤:

    观察要证线段在哪两个可能全等的三角形中,然后证这两个三角形全等。

    若图中没有全等三角形,可以把求证线段用和它相等的线段代换,再证它们所在的三角形全等。

    如果没有相等的线段代换,可设法作辅助线构造全等三角形。

      规律26

      在一个图形中,有多个垂直关系时,常用同角(等角)的余角相等来证明两个角相等。

      规律27

      三角形一边的两端点到这边的中线所在的直线的距离相等。

        规律28

      条件不足时延长已知边构造三角形。

      规律29

      连接四边形的对角线,把四边形问题转化成三角形来解决问题。

      规律30

      有和角平分线垂直的线段时,通常把这条线段延长。可归结为角分垂等腰归

      规律31

      当证题有困难时,可结合已知条件,把图形中的某两点连接起来构造全等三角形。

      规律32

      当证题缺少线段相等的条件时,可取某条线段中点,为证题提供条件。

      规律33

      有角平分线时,常过角平分线上的点向角两边做垂线,利用角平分线上的点到角两边距离相等证题。

      规律34

      有等腰三角形时常用的辅助线

    作顶角的平分线,底边中线,底边高线

    有底边中点时,常作底边中线

    将腰延长一倍,构造直角三角形解题

    常过一腰上的某一已知点做另一腰的平行线

    常过一腰上的某一已知点做底的平行线

    常将等腰三角形转化成特殊的等腰三角形------等边三角形

      规律35

      有二倍角时常用的辅助线

    构造等腰三角形使二倍角是等腰三角形的顶角的外角

    平分二倍角

    加倍小角

      规律36

      有垂直平分线时常把垂直平分线上的点与线段两端点连结起来。

      规律37

      有垂直时常构造垂直平分线。

      规律38

      有中点时常构造垂直平分线。

      规律39

      当涉及到线段平方的关系式时常构造直角三角形,利用勾股定理证题。

      规律40

      条件中出现特殊角时常作高把特殊角放在直角三角形中。

    四边形部分

      规律41

      平行四边形的两邻边之和等于平行四边形周长的一半。

      规律42

      平行四边形被对角线分成四个小三角形,相邻两个三角形周长之差等于邻边之差。

      规律43

      有平行线时常作平行线构造平行四边形。

      规律44

      有以平行四边形一边中点为端点的线段时常延长此线段。

      规律45

      平行四边形对角线的交点到一组对边距离相等。

           规律46

      平行四边形一边(或这边所在的直线)上的任意一点与对边的两个端点的连线所构成的三角形的面积等于平行四边形面积的一半。

      规律47

      平行四边形内任意一点与四个顶点的连线所构成的四个三角形中,不相邻的两个三角形的面积之和等于平行四边形面积的一半。

      规律48

      任意一点与同一平面内的矩形各点的连线中,不相邻的两条线段的平方和相等。

      规律49

      平行四边形四个内角平分线所围成的四边形为矩形。

      规律50

      有垂直时可作垂线构造矩形或平行线。

    --End--

    综合整理:中学教师联盟图文来源:网络免责声明:中学教师联盟始终尊重原创,如有侵权请联系删除

    2a4eeecc8458a367c2bb09765ac3ac80.png

    展开全文
  • 对于给定的n个位于同一二维平面上的点,求最多多少个点位于同一直线上 解题过程分析: 1、用穷举法考虑在同一条直线上的点的相同点:斜率相同。 2、但是如果直接使用除法的话,可能会出现由于四舍五入带来的精度...

    一、穷举法解题

    对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上
    解题过程分析:
    1、用穷举法考虑在同一条直线上的点的相同点:斜率相同。
    2、但是如果直接使用除法的话,可能会出现由于四舍五入带来的精度问题。
    3、考虑用乘法代替除法。
    4、点重合怎么办,找重合的点。

    import java.util.*;
    
    /*
     * public class Point {
     *   int x;
     *   int y;
     * }
     */
    
    public class Solution {
        /**
         * 
         * @param points Point类一维数组 
         * @return int整型
         */
        public int maxPoints (Point[] points) {
            // write code here
          int len=points.length;
          if(len<=2||points==null)
            return len;
          int maxp=0;
          //如果第i个和第j个点在第一条直线上,判断和他们两在同一条直线上的点的个数
          for(int i=0;i<len-1;i++){
            int count=0;
            int x=points[i].x;
            int y=points[i].y;
            int xx=x-points[i+1].x;
            int yy=y-points[i+1].y;
            //如果两个点重合
            if(xx==0&&yy==0){
              for(int j=0;j<len;j++){
                if(x==points[j].x&&y==points[j].y)
                  count++;
              }
            }else{
              for(int j=0;j<len;j++){
                if(yy*(x-points[j].x)==xx*(y-points[j].y))
                  count++;
              }
            }
            maxp=Math.max(count,maxp);
          }
          return maxp;
        }
    }
    
    展开全文
  • 平面内,与直线之间的位置关系分为两种:①在线在线外同一平面内,两条或多条不重合的直线之间的位置关系只有两种:①相交②平行一、相交线1、两条直线相交,且只有一交点。(反之,若两条直线只有一...
  • 在数学考试中,很多同学一遇到几何题就犯难。...线、角、相交线、平行线规律1如果平面上有n(n≥2)个点,其中任何三点都不在同一直线上,那么每两点画一条直线,一共可以画出n(n-1)条。规律2平面上...
  • 数姐说都说几何难,那是你没找到画辅助线的规律,一起来看看这99规律,对几何做题一定大有帮助…(在公众号对话框回复关键词“知识”,即可领取初一上册+初二上册+初三全册资料包)-01-规律1如果平面上有n(n≥2)个点,...
  • 给定平面上n个点,任意做一条直线,求至多能有几个点恰好落在直线上。 输入: 包含多组测试数据,每组测试数据由一个整数n(0 接下去n行每行给出一个点的坐标(x,y),x、y的绝对值均小于等于100。
  • 平面上有若干个点,要你找出一条直线,使其能穿过最多的点。 思路:枚举法。求出任意两点之间的线,以直线(斜率,与y轴的交点坐标)的形式存储到map。这样个数最多的直线就是所求。时间O(N^2),空间O(N). 注意...
  • 平面上n个点,求一条直线最多有几个点。 第一反应是 两两结合,获取直线,判断其他点在不在直线上,复杂度n^3 注意相同的点算是两个点,所以只在第二层循环过滤相同的点,且需要记下有几个相同的点 package...
  • Given n points on a 2D plane, find the ...在平面上n个点,求一条直线最多有几个点。 第一反应是 两两结合,获取直线,判断其他点在不在直线上,复杂度n^3 &lt;?php class Point { private $x; ...
  • 与直线之间的位置关系分为两种:① 在线在线外同一平面内,两条或多条不重合的直线之间的位置关系只有两种:① 相交 ② 平行一、相交线1、两条直线相交,且只有一交点。(反之,若两条直线只有一...
  • 注意: 1.本博客仅供参考交流使用,请读者务必自行实践,切勿生搬硬套 ...100)的点,现要求判断这组输入的点的坐标之中,最多有几个点是在同一y=kx直线上。PS:每组测试用例中不同斜率k的个数不超过...
  • leetcode之N点成线问题

    2017-04-03 09:00:28
    平面上任意N点,其中一条直线最多几个点,这个题显然O(n^2)的解法,关键的一点是一定要注意cornercase,比较多,我试了7,8次才过….首先考虑相同的点,这个要单独列出来,其次考虑不能用double表示斜率,用一个pair表示...
  • 第(1)题 max-points-on-a-line 知识点:穷举 题述:Given n points on a 2D plane, ...大意就是给定的n个点在二维平面上,求在同意条直线上的点最多有几个。 思路:两点可以确定一条直线,用斜率来判断第三个点是
  • 【ICPC-114】uva 270 - Lining Up

    千次阅读 2012-08-17 00:32:24
    题目意思: 给定平面上n个点,要求在同一条直线最多几个 解题思路: 枚举所有解 1:三个点共线的性质:A(X1,Y1),B(X2,Y2),C(X3,Y3);这个时候(Y2-Y1)/(X2-X1) = (Y3-Y1)/(X3-X1),我们知道对于double类型是...
  • uva 270 - Lining Up

    2012-08-17 00:32:00
    题目意思: 给定平面上n个点,要求在同一条直线最多几个 解题思路: 枚举所有解 1:三个点共线的性质:A(X1,Y1),B(X2,Y2),C(X3,Y3);这个时候(Y2-Y1)/(X2-X1) = (Y3-Y1)/(X3-X1),我们知道对于double类型是...
  • Google面试题(收集)

    千次阅读 2008-02-18 12:19:00
    一个random number generator,是生成真实的随机数,而不是伪... 平面上N个点,求一条直线,穿过的点数最多 Given 1 GB memory, input a file which contians 4 billion integers, output one integer that is not
  • Hdu 1432-Lining Up

    2015-10-05 16:28:04
    题意:2D平面上N个点,坐标都是整数,问最多有多少个点能落在同一条直线上。最直接的做法是O(N^3),直接枚举任意两点组成的直线,再统计跟它们共线的点。 但这个题目N,那么N^3=700*700*700=3.43*10^8,在TL为1S的...
  • 3.5.7 平面11个点,由它们连成48不同的直线,由这些点可连成多少个三角形? 腾讯篇 Java基础 4.1.0 JAVA中的种基本数据类型是什么,各自占用多少字节。 4.1.1 String类能被继承吗,为什么。 4.1.2 ...
  • CAD快捷键文档

    2011-12-17 19:02:10
    当AutoCAD正在运行的时候,我们可以通过命令行的方式,用ACAD.PGP文件里定义的快捷命令来完成一操作,比如我们要画一条直线,只需要在命令行里输入字母“L”即可。 二、快捷命令的命名规律 1、 快捷命令通常是...

空空如也

空空如也

1 2
收藏数 22
精华内容 8
关键字:

平面上有n个点最多几条直线