给你n条直线,不会存在三线共点,输出所有的可能交点数..
思路:
这个是个地推的题目,假设当前的线段i,他里面有r条是随意的,有(i - r)条是平行的,那么当前的交点数就是 r条随意的交点数 + (i - r) * r,枚举所有的r条的交点数,mark所有的 r的交点数 + (i - r) * r,具体看代码.
#include<stdio.h> #include<string.h> int mark[25][200]; void mk_mark() { //num[k] + (i - k) * k memset(mark ,0 ,sizeof(mark)); int i ,j ,k; for(i = 1 ;i <= 20 ;i ++) mark[i][0] = 1; for(i = 2 ;i <= 20 ;i ++) for(j = 1 ;j < i ; j ++) for(k = 0 ;k <= j * (j - 1) / 2 ;k ++) if(mark[j][k]) mark[i][k + (i - j) * j] = 1; } int main () { int i ,n; mk_mark(); while(~scanf("%d" ,&n)) { for(i = 0 ;i <= n * (n - 1) / 2 ;i ++) { if(mark[n][i]) { if(!i) printf("%d" ,i); else printf(" %d" ,i); } } printf(" "); } return 0; }