首页 > 代码库 > 计算直线的交点数

计算直线的交点数

2024-08-10 05:04:40   220人阅读

 计算直线的交点数

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 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 }
View Code

 

计算直线的交点数


联系
我们