首页 > 其他分享 >149. 直线上最多的点数

149. 直线上最多的点数

时间:2023-07-01 20:44:40浏览次数:36  
标签:直线 cnt res pa 149 pb pc points 点数

难度困难

给你一个数组 points ,其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

 

示例 1:

输入:points = [[1,1],[2,2],[3,3]]
输出:3

示例 2:

输入:points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出:4

 

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        cnt = 0
        res = 1
        for i in range(n):
            pa = points[i]
            for j in range(i+1,n):
                pb = points[j]
                cnt = 2
                for k in range(j+1,n):
                    pc = points[k]
                    # 直线线的两点式方程(y-y1)/(x-x1)=(y-y2)/(x-x2),再对角相乘就可以了
                    s1 = (pc[1]-pa[1]) * (pc[0]-pb[0])
                    s2 = (pc[0]-pa[0]) * (pc[1]-pb[1])
                    if s1==s2:
                        cnt+=1
                res = max(res,cnt)
        return res     

 

 

标签:直线,cnt,res,pa,149,pb,pc,points,点数
From: https://www.cnblogs.com/zle1992/p/17519902.html

相关文章

  • 直线导轨的技术应用
    直线导轨是机械领域中使用广泛的一种构件,主要用于机器的移动和定位。它具有高精度、高刚性和耐磨损等优点,被广泛应用于工业制造、医疗设备、半导体设备等领域。现在,我们来详细了解一下直线导轨的技术应用。1、移动装置,直线导轨作为机器的移动装置,可以实现机器的加工、检测和组装等......
  • opencv: 直线拟合,输出截距与偏移
    参考网页:(19条消息)OpenCV|直线拟合fitline函数(Python)_cv2.fitline_lovetaozibaby的博客-CSDN博客我的例子:   ......
  • 浮点数-Float-Double转二进制在线工具
    浮点数-Float-Double转二进制Float转二进制,Double转浮点数-Float-Double转二进制https://tooltt.com/floatconverter/在线单双精度(Float,Double)浮点数转二进制浮点数,是属于有理数中某特定子集的数的数字表示,在计算机中用以近似表示任意某个实数。具体的说,这个实数由一......
  • 编程初学者入门5_键盘输入5个人的身高(米),求他们的平均身高(米)。(C的没问题,试着用Java写
    写在前面此系列博客为牛客网编程初学者入门题目小结,题目很基础不常用的知识容易遗忘,为了边复习c语言和学习Java,后面系列博客将采用c、c++、Java双语言版记录现在位置(72/140),虽然我走的很慢,但我仍在前进~题目描述从键盘输入5个人的身高(米),求他们的平均身高(米)。输入描述:一行,连续输......
  • 直线一般式拟合直线
    为了防止忘记,特转载至此。本文方法来源是《最小二乘法直线拟合:Ax+By+C=0-会飞的大象会飞的大象(whudj.cn)》。用一次函数${y=kx+b}$形式拟合直线非常简单,直接带入最小二乘法公式就行了。而用直线一般式${ax+by+c=0}$拟合由于不是线性方程组则需要一些求解技巧。这里不再重......
  • 直线导轨在焊接领域有什么作用?
    焊接技术在现代制造业中的应用越来越广泛,直线导轨作为重要的传动元件,已经成为焊接设备中不可或缺的部分。相对于直线轴承来说,直线导轨具有较高的负载能力和刚度,能够保证高精度的直线运动,滑动摩擦小,惯量小,能够实现高速运动;摩擦小、磨损小,噪音低、寿命长,能有效减少能量损耗,有利于节能......
  • Android Bresenham 直线算法 让你的手势更丝滑
    Bresenham算法是一种用于绘制直线的算法,它通过在离散的像素点上进行逐步的迭代来绘制出近似直线。以下是一个示例代码,演示了如何使用Bresenham算法绘制直线:fundrawLine(x0:Int,y0:Int,x1:Int,y1:Int){valdx=Math.abs(x1-x0)valdy=Math.abs(y1-......
  • 计算机计算浮点数出现的误差
    foriinrange(20):print(f"0.1*{i}={0.1*i}")0.1*0=0.00.1*1=0.10.1*2=0.20.1*3=0.300000000000000040.1*4=0.40.1*5=0.50.1*6=0.60000000000000010.1*7=0.70000000000000010.1*8=0.80......
  • 直线模组在工业自动化领域中的作用和使用
    中国工业制造业快速发展,工业自动化领域也进入了飞速发展的阶段,直线模组作为工业自动化领域不可缺少的机器人之一,有着重要的不可或缺的作用。那直线模组在工业自动化行业中主要有什么作用呢?接下来我们来看看:1>半导体行业2>3C电子行业3>锂电行业4>焊接工程5>显示面板行业6>医疗行业7>......
  • 1494. 并行课程 II (Hard)
    问题描述1494.并行课程II(Hard)给你一个整数n表示某所大学里课程的数目,编号为1到n,数组relations中,relations[i]=[xᵢ,yᵢ]表示一个先修课的关系,也就是课程xᵢ必须在课程yᵢ之前上。同时你还有一个整数k。在一个学期中,你最多可以同时上k门课,前提是这......