-
给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上。
2018-12-26 09:08:34需求:给定一个二维平面,平面上有 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) #输出去重完毕后的列表,再经过一次遍历即可找出最多点所在的直线
-
C++求平面上不重合的n个点最多构成多少条两两互不平行(包括重合)的直线
2020-08-15 08:28:28对应题目 UPC NO.78场 问题 E: 阅兵队形 plane ...在所有直线中应该最少删除多少条直线使得剩下的直线两两都不相互平行(重合也是平行)。 求出最多可以构成多少条两两互不平行的直线。 输入 第一行,整对应题目
UPC NO.78场 问题 E: 阅兵队形 plane
题目描述
70 周年阅兵的时候,飞机在空中排练着队形,Yyx 很好奇,他想知道这么训练有素的队形到底是如何造就的呢?他记录下了飞行路径上的各个端点。
他发现:把整个天空看做一个平面直角坐标系,飞行路径是所有过任意两个端点的直线。
如果这些飞机可能会撞在一起,或者说只要这些直线有交点,就可能发生事故。
在所有直线中应该最少删除多少条直线使得剩下的直线两两都不相互平行(重合也是平行)。
求出最多可以构成多少条两两互不平行的直线。输入
第一行,整数 n。
接下来 n 行,每行两个整数 x,y,表示这个端点的横坐标与纵坐标。
输出
一行,一个整数 ans,表示答案。样例输入
4
-1 1
-2 0
0 0
1 1
样例输出
4提示
对于所有数据,2≤N≤200,-1000≤Xi≤1000,-1000≤Yi≤1000。
在所有直线中应该最少删除多少条直线使得剩下的直线两两都不相互平行。题意:
在坐标纸上有N个不重合的点,两两可以连一个线段并延伸成直线,请问在这些直线里最多能选出多少条使得他们两两不平行也不重合(题目可能有点饶头,要求的就是题目描述的最后一行,它的上面一句和样例的提示纯属出自出题人的 “善意”…)。下面2种算法思路的直线都是通过n^2枚举出来的
思路1:
首先讲一种常见的思路:运用斜率+特判来解决问题。
具体做法:
考虑斜率k
特判直线垂直于x轴的情况(k负一个特殊值)
用map进行判断#include<bits/stdc++.h> using namespace std; int n,ans,x1[520],y1[520]; map<double,bool>f; int main() { cin>>n; for(int i=1; i<=n; i++) cin>>x1[i]>>y1[i]; for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++) { int lx = x1[i]-x1[j]; int ly = y1[i]-y1[j]; double k; if(lx==0) k=5.25; else k = (double)ly/lx; if(!f[k]) {f[k]=1; ans++;} } cout<<ans<<endl; return 0; } /* 另一写法:求出每两个点间的斜率,排序后判断 #include<bits/stdc++.h> #define N 201 #define eps 1e-6 #define PI acos(-1.0) using namespace std; struct Point {double x, y;} p[N]; double a[N*N]; int n; double FindSlewRate(Point p1, Point p2) { Point p; p.x = p2.x-p1.x; p.y = p2.y-p1.y; if(abs(p.x)<eps) return PI/2; //斜率不存在 double tmp = atan(p.y/p.x); if(tmp<0) return PI+tmp; return tmp; } int cmp(const void *c, const void *d){ return *(double *)c > *(double *)d ? 1:-1; } int main() { while(~scanf("%d", &n)) { for(int i=0; i<n; i++) scanf("%lf%lf", &p[i].x, &p[i].y); int rt=0; for(int i=0; i<n; i++) for(int j=i+1; j<n; j++) a[rt++] = FindSlewRate(p[i], p[j]); qsort(a,rt,sizeof(a[0]),cmp); int ans=1; for(int i=1; i<rt; i++) if(a[i] != a[i-1]) ans++; printf("%d\n", ans); } return 0; } */
思路2:
再介绍一种运用向量的做法:考虑使用向量进行判断两点是否平行
具体做法:
需要对向量进行特殊处理
1.首先让x不小于0
2.如果x==0那么y就取绝对值
3.x , y 除以 (x , y) 的绝对值的最大公因数
这样的话,每一种方向的向量就只有唯一的表示方法
用桶进行判断(注意y可能为负)#include<bits/stdc++.h> using namespace std; int x[520],y[520]; bool flag[5200][5200]; int n,ans; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>x[i]>>y[i]; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { int lx=x[i]-x[j]; int ly=y[i]-y[j]; if(lx<0) { lx = -lx; ly = -ly; } else if(lx==0) ly=abs(ly); int gcd = __gcd(lx,abs(ly)); lx /= gcd; ly /= gcd; if(!flag[lx][ly+2005]) { ans++; flag[lx][ly+2005] = 1; } } cout<<ans<<endl; return 0; }
-
计算N条直线所有可能的交点个数(动态规划)
2013-01-14 11:37:21平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数。 比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。 问题分析 将n条直线排成一个序列,直线2和直线1最多只有一个交点,直线3和直线1,2...计算直线的交点数
Problem Description
平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数。
比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。问题分析
将n条直线排成一个序列,直线2和直线1最多只有一个交点,直线3和直线1,2最多有两个交点,……,直线n 和其他n-1条直线最多有n-1个交点。由此得出n条直线互不平行且无三线共点的最多交点数:
Max = 1 +2 +……+(n-1)=n(n-1)/2;
这些直线有多少种不同的交点数
当n = 1, 2, 3时情况很容易分析。当n = 4 时,我们可以按如下分类方法,逐步计算。
1. 四条直线全部平行,无交点。
2. 其中三条平行,交点数: 3*(n-3)+0 = 3;
3. 其中两条平行,而另外两条直线的交点既可能平行也可能相交,因此交点数据分别为:
2*(n-2) + 0 = 4
2*(n-2) + 1 = 5
4. 四条直线互不平行, 交点数为1*(n-1) + {3条直线的相交情况}:
1*(n-1)+0=3
1*(n-1)+2=5
1*(n-1)+3=6即n=4时,有0, 3, 4, 5, 6个不同的交点数.所以有5种可能。
从上述n=4的分析过程中,发现:
m条直线的交点数=r条平行线与m-r条直线交叉的交点数+ m-r条直线本身的交点数 =r*(m-r) + m-r条直线之间的交点数。(1<=r<=m)
{m条直线的交点数集合} = U { r条平行线与m-r条直线交叉的交点数 + {m-r条直线本身的交点数集合} } = U { r*(m-r) + {m-r条直线之间的交点数集合} }。(1<=r<=m)
注意:数和集合相加 = 数和集合中每个元素相加组成的新集合。
如何编写程序?
程序框架如下:
//Ui表示i条直线的交点数集合
初始化U0= {0}, U1= {0}
For n = 2 to N
Un = {} //初始化Un 为空集
For i = 1 to n //i表示平行线个数
Un =Un U { i*(n-i) + Un-i} //并运算
注意:数和集合相加 = 数和集合中每个元素相加组成的新集合。
用C++代码实现,我们可以用set集合,最简单的方法是用数组表示交点数集合。
二维数组 p[i][j] 表示i条直线,j个交点数是否存在。存在值为1,不存在值为0.
#include <stdio.h>
int main()
{
int p[21][200], n; //200为交点数的上限,交点数为1+2+3+…(n-1)
memset(p, 0, sizeof(p));
for(int i=0; i<21; i++)
p[i][0]=1; //不管多少直线都存在0个交点的情况,即所有直线平行
for(int n=2; n<21; n++) //动态规划p[i][j]表示i条直线,交点数为j.当 p[i][j]=1,则表示i条直线中,存在交点数为j的情况
for(int i=1; i < n; i++) //n条直线平行的情况已经考虑了,无需重复
for(int j=0; j<200; j++)
{
if(p[n-i][j]==1)
p[n][j+i*(n-i)]=1;}
while (scanf("%d", &n) != EOF)
{
for (j=0; j <= n*(n-1)/2; j++) //n*(n-1)/2能形成的最大交点数
{
if (f[n][j])
printf("%d ",j);
}
printf("\n");
}
return 0;}
这个是转载别人的,感觉好强大,我一直在想:我怎么当我知道i(n-i)条直线平行时,我又怎么可以把n-i条剩余的直线的所有可能加上去呢。加上去后我怎么存储呢?
而这个程序他运用了逆向的思想,从头到尾做出了所有可能的表格 。要不然怎么叫做规划呢?而且还是动态的?
首先他用i行表示多少条线,用数组元素为1表示该元素的j为可能存在的交点个数。
然后从数组2行开始往后规划,规划的方法是:i条线平行。n-i条线得出行数存在的交点情况加上i(n-i),然后在相应得到交点数赋值为1
-
计算直线的交点数
2014-04-01 19:06:12平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数。 比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。 问题分析 将n条直线排成一个序列,直线2和直线1最多只有一个交点,直线3和直线1,2最多...计算直线的交点数
Problem Description
平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数。
比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。问题分析
将n条直线排成一个序列,直线2和直线1最多只有一个交点,直线3和直线1,2最多有两个交点,……,直线n 和其他n-1条直线最多有n-1个交点。由此得出n条直线互不平行且无三线共点的最多交点数:
Max = 1 +2 +……+(n-1)=n(n-1)/2;
这些直线有多少种不同的交点数
当n = 1, 2, 3时情况很容易分析。当n = 4 时,我们可以按如下分类方法,逐步计算。
1. 四条直线全部平行,无交点。
2. 其中三条平行,交点数: 3*(n-3)+0 = 3;
3. 其中两条平行,而另外两条直线的交点既可能平行也可能相交,因此交点数据分别为:
2*(n-2) + 0 = 4
2*(n-2) + 1 = 5
4. 四条直线互不平行, 交点数为1*(n-1) + {3条直线的相交情况}:
1*(n-1)+0=3
1*(n-1)+2=5
1*(n-1)+3=6即n=4时,有0, 3, 4, 5, 6个不同的交点数.所以有5种可能。
从上述n=4的分析过程中,发现:
m条直线的交点数=r条平行线与m-r条直线交叉的交点数+ m-r条直线本身的交点数 =r*(m-r) + m-r条直线之间的交点数。(1<=r<=m)
{m条直线的交点数集合} = U { r条平行线与m-r条直线交叉的交点数 + {m-r条直线本身的交点数集合} } = U { r*(m-r) + {m-r条直线之间的交点数集合} }。(1<=r<=m)
如何编写程序?
程序框架如下:
//Ui表示i条直线的交点数集合
初始化U0= {0}, U1= {0}
For n = 2 to N
Un = {} //初始化Un为空集
For i = 1 to n //i表示平行线个数
Un =Un U { i*(n-i) + Un-i} //并运算
注意:数和集合相加 = 数和集合中每个元素相加组成的新集合。
用C++代码实现,我们可以用set集合,最简单的方法是用数组表示交点数集合。
二维数组 p[i][j] 表示i条直线,j个交点数是否存在。存在值为1,不存在值为0.
#include <stdio.h>
int main()
{
int p[21][200], n; //200为交点数的上限,交点数为1+2+3+…(n-1)
memset(p, 0, sizeof(p));
for(int i=0; i<21; i++)
p[i][0]=1; //不管多少直线都存在0个交点的情况,即所有直线平行
for(int n=2; n<21; n++) //动态规划p[i][j]表示i条直线,交点数为j.当 p[i][j]=1,则表示i条直线中,存在交点数为j的情况
for(int i=1; i < n; i++) //n条直线平行的情况已经考虑了,无需重复
for(int j=0; j<200; j++)
{
if(p[n-i][j]==1)
p[n][j+i*(n-i)]=1;}
while (scanf("%d", &n) != EOF)
{
for (j=0; j <= n*(n-1)/2; j++) //n*(n-1)/2能形成的最大交点数
{
if (f[n][j])
printf("%d ",j);
}
printf("\n");
}
return 0;}
-
计算直线的交点数—动态规划
2011-07-26 00:02:43计算直线的交点数Problem Description平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数。比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。问题分析将n条直线排成一个序列,直线2和直线1最多... -
直线分割平面(动态规划递推)
2018-11-05 09:03:00在一个平面上有一个圆和n条直线,这些直线中每一条在圆内同其他直线相交,假设没有3条直线相交于一点,试问这些直线将圆分成多少区域。 /* 思路: n=1时有两个平面 这时让n=2,多一条直线,这条直线最多与n-1条... -
hdu1466 计算直线的交点数
2013-07-26 14:26:56平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数。 比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。 分析: DP 设状态:f[i][j]表示i条直线能否产生j个交点。 有不同的交点数--->n条... -
计算直线的交点方案数
2017-03-20 14:41:44平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数。 输入:n(n) 输出:每个测试实例对应一行输出,从小到大列出所有相交方案,其中每个数为可能的交点数。 样例输入 4 样例输出 0 3 4 5 6 ... -
直线划分平面问题
2012-11-13 14:52:26n条直线最多能划分出多少个平面? 问题分析: 平面上只要多出现一条直线,就能至少多把平面分出一部分,而若此直线与其他直线有n个交点,就再能把平面多分出n个部分,因此若想把平面划分的部分最多,新添入的... -
hdu 1466 计算直线的交点数(动态规划)
2013-09-26 19:36:55平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数。 比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。 输入:n(n 输出:每个测试实例对应一行输出,从小到大列出所有相交方案,其中每个数为... -
直线(大数乘法)
2020-05-31 16:06:29来源:牛客网 平面上存在n条直线。请问n条直线在平面上最多存在多少交点。...对于每组输入样例,打印n条直线最多有多少个交点 示例1 输入 复制 2 1 2 输出 复制 0 1 #include <bits/stdc++.h> using namespac -
点分线,线分平面,平面分空间.
2011-05-17 16:02:00题目:在一个平面上画1999条直线最多能将这一平面划分成多少个部分?分析:当有n-1条直线时,最多将平面分割成f(n-1)个平面,则要使第n条直线切成的区域数最多,就必须与每条直线相交且不能有同一交点。这样就会得到... -
折线分割平面
2017-03-18 12:48:18在一个平面上有一个圆和n条直线,这些直线中每一条在圆内同其他直线相交,假设没有3条直线相交于一点,试问这些直线将圆分成多少区域。 分析: 当添加第N条,为了使平面最多, 则第N条直线要与前面的N-1条直线... -
平面分割类问题总结
2018-01-30 11:06:00【题型一】直线分割平面在一个平面上有一个圆和n条直线,这些直线中每一条在圆内同其他直线相交,假设没有3条直线相交于一点,试问这些直线将圆分成多少区域。分析:当添加第N条,为了使平面最多, 则第N条直线要与... -
折线分割平面 学习了解!!!
2019-02-13 13:00:00【题型一】直线分割平面 在一个平面上有一个圆和n条直线,这些直线中每一条在圆内同其他直线相交,假设没有3条直线相交于一点,试问这些直线将圆分成多少区域。 分析: 当添加第N条,为了使平面最多, 则第N条直线要... -
“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛题解 H
2020-06-14 20:07:41平面上n条直线最多有1/2 * n * (n-1)个交点。 注意数据范围比较大,需要用高精。或者python/java。 代码 import sys def main(): t = int(input()) while t != 0: t -= 1 n1 = int(input()) n2 = n1 - 1 ... -
HDU 1290 献给杭电五十周年校庆的礼物
2015-06-07 15:16:00第n个直线最多和之前的n-1条直线相交,有n-1个交点,将n个平面一分为2,因此f(n)=f(n-1)+n;得到f(n)=(n+1)n/2+1; 2.计算平面最多将空间分成多少个部分: 第n个平面最多和之前的n-1个平面相交,这些平面上最多有n-.... -
大数乘法
2020-06-02 11:31:21对于每组输入样例,打印n条直线最多有多少个交点 示例1 输入 复制 2 1 2 输出 复制 0 1 链接:https://ac.nowcoder.com/acm/contest/5758/H #include <stdio.h> #include <string.h> i -
面试小算法_2
2012-11-05 19:56:221. 有两根不均匀分布的香,每根香烧完的时间是一个小时,你能用什么方法来确定一段15分 ...平面上只要多出现一条直线,就能至少多把平面分出一部分,而若此直线与其他直线有n个交点,就再能把平面多分出n个部分 -
【BZOJ1580】【USACO2009Hol】杀手游戏 计算几何
2017-11-03 21:45:17这样每个其他的点的运动轨迹就可以看成一条直线,要求出最多有多少个点同时在圆内。然后就是求直线和圆的交点。然后把这些交点按照时间排序,第一次出现就是进入,第二次出现就是出去。直接扫一遍就
-
MySQL 事务和锁
-
光学学报1986年第6卷第11期 目录
-
零基础极简以太坊智能合约开发环境搭建并开发部署
-
MySQL 多平台多模式(安装、配置和连接 详解)
-
权益法工具-源码
-
java 井字棋 人机_井字棋(人机对战版)
-
jdk中常用JAVA类_Java 常用类
-
preg_replace在java中_PHP中一个有趣的preg_replace函数详解
-
LVS + Keepalived 实现 MySQL 负载均衡与高可用
-
加利福尼亚和内华达州-源码
-
C语言零基础入门(详细讲解)
-
个人网站-源码
-
presto联合查询mysql和ES_presto-mysql、presto-elasticsearch、关联查询、java-presto-jdbc入门实战....
-
xxljob源码分析
-
ppt中的流程图怎么整体移动_ppt中的流程图怎么整体移动_PPT中的这种图片分割效果,该怎么搞?...
-
terraexam-aws-rds-mysql-源码
-
Galera 高可用 MySQL 集群(PXC v5.6 + Ngin
-
java 两个arraylist 比较_比较Java中两个arrayList的元素
-
presto java_java 连接presto实现SQL查询
-
SpringBoot中多数据源配置Mybatis驼峰命名不管用,带下划线字段返回为null