精华内容
下载资源
问答
  • // 思路: 就是问最多有多少个点在同一条直线上.思路:肯定联想到用斜率或者向量的形式来求呀, 所以我们用向量方便一点, 我们任取个点作为基准点, 算出一个向量(x1, y1), 然后枚举第三个点, 算第二个点和第三个点的...

    传送门
    // 思路: 就是问最多有多少个点在同一条直线上.

    思路:肯定联想到用斜率或者向量的形式来求呀, 所以我们用向量方便一点, 我们任取两个点作为基准点, 算出一个向量(x1, y1), 然后枚举第三个点, 算第二个点和第三个点的之间的向量, 然后通过判断向量是否平行的方式来判断这三点是否处于同一直线上, 也就是 x1*y2 == x2*y1…. 复杂度O(n^3), 这题数据弱让我卡过去了, 也许这个OJ1s能跑1e9了? (逃

    AC Code

    const int maxn = 7e2+5;
    pii po[maxn];
    void solve()
    {
        int n;
        scanf("%d", &n);
        for (int i = 1 ; i <= n ; i ++) {
            scanf("%d%d", &po[i].fi, &po[i].se);
        }
        int ans = 0;
        for (int i = 1 ; i <= n ; i ++) {
            for (int j = i+1 ; j <= n ; j ++) {
                int cnt = 2;
                int x1 = po[i].fi - po[j].fi;
                int y1 = po[i].se - po[j].se;
                for (int k = 1 ; k <= n ; k ++) {
                    if (k == i || k == j) continue;
                    int x2 = po[j].fi - po[k].fi;
                    int y2 = po[j].se - po[k].se;
                    if (x1*y2 == x2*y1) cnt++;
                }
                ans = max(ans, cnt);
            }
        }
        printf("%d\n", ans);
    }
    展开全文
  • 需求:给定一个二维平面,平面上有 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)
    #输出去重完毕后的列表,再经过一次遍历即可找出最多点所在的直线
    
    展开全文
  • 思路一:两点确立一条直线,判断其余的点是否在直线上;时间复杂度o(n^3) Submission Result: Time Limit Exceeded int maxPoints(vector &points) { vector vi=points; int xi,yi; int xj,yj; unsigned ...

    思路一:两点确立一条直线,判断其余的点是否在直线上;时间复杂度o(n^3)

    Submission Result: Time Limit Exceeded

    int maxPoints(vector<Point> &points) {
        vector<Point> vi=points;
    	int xi,yi;
    	int xj,yj;
    	unsigned int i,j,k;
    	int num=0;
    	int max=0;
    	int temp1,temp2,temp3,temp4,temp5;
    	if(vi.size()==0)
    		return 0;
    	else if(vi.size()>0&&vi.size()<=1)
    		return 1;
    	else if(vi.size()==2)
    		return 2;
    
    	for(i=0;i<vi.size();i++)
    	{
    		num=1;
    		xi=vi[i].x;
    		yi=vi[i].y;
    		for(j=i;j<vi.size();j++,num=2)
    		{
    			if(j==i)
    				continue;
    			xj=vi[j].x;
    			yj=vi[j].y;
    			num=2;
    			temp1=xj-xi;
    			temp2=yj-yi;
    			for(k=0;k<vi.size();k++)
    			{
    				if(k==i)
    					continue;
    				if(k==j)
    					continue;
    
    				//if(((yj-yi)*(vi[k].x-xi)/(xj-xi)+yi)==vi[k].y)
    				//temp1=(yj-yi)*(vi[k].x-xi);
    				if(temp1==0&&temp2==0)
    				{
    				    if(xj==vi[k].x)
    				        {num++;
    				        continue;}
    				}
                    else{
    					temp3=temp2*vi[k].x+vi[i].y*vi[j].x-vi[j].y*vi[i].x;
    					temp4=temp1*vi[k].y;
    					if(temp3==temp4)
    					num++;
                    }
    
    
    			}
    			if(num>max)
    				max=num;
    
    		}
    	}
    
    	return max;
            
        }

    思路二:记下任意两点的斜率(不要是整形,float或double ),找出最多能有多少个点斜率相同,
    注意处理一些特殊情况,如斜率为正无穷,或存在相同的点对

    accept代码:
    int maxPoints(vector<Point> &points) 
    {
    	 int mx =1e10;
    	size_t i,j;
    	int xx,yy;
    	int sam=0;
    	int max_num=0;
    	map<double,int> m;
    	//m.clear();
    	if(points.size()==0)
    		return 0;
    	else if(points.size()==1)
    		return 1;
    	else if(points.size()==2)
    		return 2;
    
    
    	for(i=0;i<points.size();i++)//如果vector中有三个以上的点
    	{
    		m.clear();
    		sam=0;//用于记录有多少一样的点
    		for(j=i;j<points.size();j++)
    		{
    			double k;
    			xx=points[j].x-points[i].x;
    			yy=points[j].y-points[i].y;
    			if(xx==0&&yy==0)//两个点相同
    				{
    					sam++;
    					continue;
    				}
    			else if(xx==0)//两点确立的直线平行于y轴,它的斜率为正无穷,用mx表示
    				k=mx;
    			else
    				k=double(yy)/xx;//一般情况计算两点的斜率,注意区分k=double(yy/xx)
    
    			m[k]++;
    
    		}
    		if(m.size()==0)
    		{
    			if(sam>max_num)
    				max_num=sam;
    
    			continue;
    		}
    
    		map<double,int>::iterator it=m.begin();//遍历m
    		for(it;it!=m.end();it++)
    		{
    			if((*it).second+sam>max_num)
    				max_num=(*it).second+sam;
    		}
    		
    	}
    
    	return max_num;
    }
    



    展开全文
  • 两条直线的交点,只需把这个二元一次方程联立求解,当这个联立方程组无解时,直线平行;有无穷多解时,直线重合;只有一解时,直线相交于一点。常用直线向上方向与 X 轴正向的 夹角( 叫直线的倾斜角 )或...

    这里就要介绍一个概念:直线方程


    直线方程

    从平面解析几何的角度来看,平面上的直线就是由平面直角坐标系中的一个二元一次方程所表示的图形。求两条直线的交点,只需把这两个二元一次方程联立求解,当这个联立方程组无解时,两直线平行;有无穷多解时,两直线重合;只有一解时,两直线相交于一点。常用直线向上方向与 X 轴正向的 夹角( 叫直线的倾斜角 )或该角的正切(称直线的斜率)来表示平面上直线(对于X轴)的倾斜程度。可以通过斜率来判断两条直线是否互相平行或互相垂直,也可计算它们的交角。直线与某个坐标轴的交点在该坐标轴上的坐标,称为直线在该坐标轴上的截距。直线在平面上的位置,由它的斜率和一个截距完全确定。在空间,两个平面相交时,交线为一条直线。因此,在空间直角坐标系中,用两个表示平面的三元一次方程联立,作为它们相交所得直线的方程。


    在这里我们只需要用到直线方程的部分性质
    直线方程的一般式为:ax+by+c=0ax+by+c=0
    在平面直角坐标系中,我们知道任意两个点的坐标就可求出经过这两个点的直线方程
    可得:

    a=y2-y1
    b=x1-x2//注意别写反了
    c=-ax1+by1

    显然只需要代入其他点判断是否满足一般式即可

    相关题目:洛谷1142轰炸

    此题代码:

    #include<bits/stdc++.h>
    using namespace std;
    const int MAXN=710;
    int read()
    {
        int sum=0,flag=1;
        char c;
        for(;c<'0'||c>'9';c=getchar())if(c=='-') flag=-1;
        for(;c>='0'&&c<='9';c=getchar())sum=(sum<<1)+(sum<<3)+c-'0';
        return sum*flag;
    } 
    int n;
    int x[MAXN],y[MAXN];
    void init()
    {
        n=read();
        for(int i=1;i<=n;++i) x[i]=read(),y[i]=read();
    }
    int ans=1;
    int num;
    int main()
    {
        init();
        for(int i=1;i<=n;++i)
        for(int j=1;j<i;++j)
        {
            int a=y[j]-y[i];
            int b=x[i]-x[j];
            int c=-a*x[i]-b*y[i];
            num=0;
            for(int k=1;k<=n;++k)
            {
                if(a*x[k]+b*y[k]+c==0) num++;
            }
            ans=max(ans,num);
        }
        printf("%d",ans);
        return 0;
    }
    展开全文
  • 开始拿到这个题的时候,首先就会想到两点确定一条直线,若要判断相应的点是否在同一条直线上,仅需求出它们的斜率即可。 但是此题需注意的几点是:(1)当斜率不存在的情况:即(y2-y1)/(x2-x1)中(x2-x1)为0的...
  • 3.max points ona line(最多有多少个点在同一...给出二维平面上的n个点,求最多有多少点在同一条直线上。   分析:中等题 任意一条直线都可以表述为 y = ax + b 假设,有个点(x1,y1), (x2,y2),如果他们都在这条
  • ###题目给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上。输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]输出: 4###思路下班回来只想睡觉,就暴力法混混得了。得出二维平面上的点能够组成的所有...
  • 地图方向与方位的判定,是地理学科的基础知识,也是地理学习的重点、如何熟练掌握地图判定方位的方法,不仅是平时生活中的一项技能,也是我们提高应试能力的一个重要法宝。 一、构建思维模式图 二、地图...
  • 平面的基本性质(1)公理1:如果一条直线上的两点在一个平面内,那么这条直线在此平面内.(2)公理2:过不在同一条直线上的三点,有且只有一个平面.(3)公理3:如果两个不重合的平面有一个公共点,那么它们有且只有一条过...
  • 立体几何基本公理体系公理1:如果一条直线上两点一个平面内,那么这条直线此平面内。符号语言: 图形语言:公理2:过不条直线上的三点,有且仅有一个平面。图形语言:推论1:一条直线和直线外的一点确定...
  • 条向量条直线上时,向量的叉积等于 0 ,即上面的第二种情况,所以判断条线段相交就分为种情况讨论:1.向量的叉积不等于 0 ;2.向量的叉积等于 0 。一.叉积不等于 0首先:我们要判断...
  • 这是书的问题 6、平面,连接两个点(x_1 〖,y〗_(1 ) )和(x_2 〖,y〗_(2 ) )的直线由如下方程定义: ax+by=c (其中,a=y_2-y_1,b=x_1-x_2,c=x_1 y_2...为什么需要判断的两点P1和P2还无法输入,就直接结束了?
  • 2.其次是如何判断多个条直线上,那就是计算斜率,如果一个和多个计算的斜率都是相同的,那就意味着这几个条直线上的 3.那么这道题的思路就已经出来了:通过层的循环,针对每个都与其他的...
  • 本文首发于“小白学视觉”微信公众号,...为了更让小伙伴更早的了解最新版的OpenCV 4,小白与出版社沟通,提前公众号连载部分内容,请持续关注小白。霍夫变换(Hough Transform)是图像处理中检测是否存在直线...
  • 问题的描述是一个二维平面有一些随机分布的散点,要求我们这些散点里找到,使得它们的距离最小。用暴力求解的方式解决这个问题很简单,只需要把所有的情况都列举出来,即计算出每一个与其他所有节点的...
  • 对于直线的同一侧的所有(x,y),实数的符号是相同的,因此我们一般是在直线的某一侧任取一点()代入,由的符号来判断>0表示的是直线哪一侧的点集,习惯将此法提炼为“直线定界、特殊定域”。这种通用方法...
  • 我们都知道,两点可以确定一条直线,而且可以写成y = ax + b的形式,条直线上的点都满足这个公式。所以这些给定点两两之间都可以算一个斜率,每个斜率代表一条直线,对每一条直线,带入所有的点看是否共线,并...
  • 我们都知道,两点可以确定一条直线,而且可以写成y = ax + b的形式,条直线上的点都满足这个公式。所以这些给定点两两之间都可以算一个斜率,每个斜率代表一条直线,对每一条直线,带入所有的点看是否共线,并...
  • 给出二维平面上的n个点,求最多有多少点在同一条直线上。 x点和y点的坐标值在-1000~1000之间 样例 1: 输入: (1,2),(3,6),(0,0),(1,3). 输出: 3 样例 2: 输入: (1,2),(2,3),(3,2). 输出: 2 原题传送门 ...
  • 题目给出二维平面上的n个点,求最多有多少点在同一条直线上。 样例给出4个点:(1, 2), (3, 6), (0, 0), (1, 3)。 一条直线上的点最多有3个。 解决思路 重复的点没有必要去增加时间复杂度, 先把point点简化成没有...
  • 给出二维平面上的n个点,求最多有多少点在同一条直线上。 样例 样例 1: 输入:(1,2),(3,6),(0,0),(1,3). 输出:3 样例 2: 输入:(1,2),(2,3),(3,2). 输出:2 注意事项 x点和y点的坐标值在-1000~1000之间 思路: 原理:...
  • 今天,给大家带来的是初中数学8大类61点易错知识,期末考试就不要再这些点上扣分啦~家长记得转给孩子!数与式易错1:有理数、无理数以及实数的有关概念理解错误,相反数、倒数、绝对值的意义概念混淆。以及...
  • 对于直线的同一侧的所有(x,y),实数的符号是相同的,因此我们一般是在直线的某一侧任取一点()代入,由的符号来判断>0表示的是直线哪一侧的点集,习惯将此法提炼为“直线定界、特殊定域”。这种通用方法...
  • 给出二维平面上的n个点,求最多有多少点在同一条直线上。 Explanation: 给出4个点:(1, 2), (3, 6), (0, 0), (1, 3)。 一条直线上的点最多有3个。 Solution: 计算斜率冰雹存在hashmap中,注意 ...
  • 给出二维平面上的n个点,求最多有多少点在同一条直线上。 样例:给出4个点:(1, 2), (3, 6), (0, 0), (1, 3)。一条直线上的点最多有3个。 算法思想:点和点在不在一条直线上,关键两点之间的斜率是否相同。开始...
  • 给出二维平面上的n个点,求最多有多少点在同一条直线上。 样例 给出4个点:(1, 2), (3, 6), (0, 0), (1, 3)。 思路借助辅助二维数组,存储每两点之间的斜率和截距。代码# Definition for a point. # class ...
  • 点在直线上的投影

    万次阅读 2014-05-23 16:42:17
    转自:求点在直线上的投影 如何求点到直线的投影,这个问题经常遇到。这里整理看到的资料写个总结。 PS:如果使用初中高中的方法...3、因为P0、P1、P2都在同一条直线上,所以可得k *(P2 - P1) = P0 - P1   
  • 思路:两点可以确定一条直线,那么选择固定一个点,求其他点与固定点的斜率,如果斜率相同,那么斜率相同的点在同一条直线上。 注意点: 1.保存斜率可以使用哈希表进行; 2.测试数据中精度要求很高,使用Double...
  • 题目描述 给定一个二维平面,平面上有 n 个点,求最多有多少个点在...穷举,算出每个点和其他各个点的斜率(若个点和同一个点的斜率相同,那么这三个点在同一条直线上),计算不同斜率点的个数(别忘了把当前点...

空空如也

空空如也

1 2 3 4 5 ... 13
收藏数 248
精华内容 99
关键字:

两点在同一条直线上