首页 > 代码库 > 计算直线的交点数
计算直线的交点数
计算直线的交点数
Time Limit: 1 Sec Memory Limit: 64 MBSubmit: 820 Solved: 518
Description
平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数。比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。
Input
输入数据包含多个测试实例,每个测试实例占一行,每行包含一个正整数n(n <= 20),n表示直线的数量.
Output
每个测试实例对应一行输出,从小到大列出所有相交方案,其中每个数为可能的交点数,每行的整数之间用一个空格隔开。
Sample Input
23
Sample Output
0 10 2 3
把m条线分成r和m-r两部分({n}只n条线时的交点方案的集合)
Pay points=r*(m-r)+{m-r},dp[i][j]为是否存在标志,
1 # include<stdio.h> 2 int main() 3 { 4 // freopen("a.txt","r",stdin); 5 int i,j,k,m,n; 6 int a[22][200]; 7 8 while(scanf("%d",&n)!=EOF) 9 {10 for(i=0;i<190;i++)11 a[0][i]=0;12 for(i=1;i<=n;i++)13 {14 a[i][0]=1;15 for(j=1;j<=(i-1)*i/2;j++)16 a[i][j]=0;17 for(j=1;j<i;j++)18 {19 m=i-j;20 for(k=0;k<=m*(m-1)/2;k++)21 {22 if(a[m][k]==1)23 a[i][k+j*m]=1;24 /* printf("%d,%d %d,%d\n",m,k,i,k+j*m);25 printf("\n");*/26 }27 }28 }29 printf("0");30 for(i=1;i<=n*(n-1)/2;i++)31 {32 if(a[n][i]==1)33 printf(" %d",i);34 }35 printf("\n");36 }37 return 0;38 }
计算直线的交点数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。