計算直線的交點數

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7923 Accepted Submission(s): 3529

Problem Description 平面上有n條直線，且無三線共點，問這些直線能有多少種不同交點數。
比如,如果n=2,則可能的交點數量為0(平行)或者1(不平行)。
Input 輸入數據包含多個測試實例,每個測試實例占一行,每行包含一個正整數n（n<=20）,n表示直線的數量.

Output 每個測試實例對應一行輸出，從小到大列出所有相交方案，其中每個數為可能的交點數,每行的整數之間用一個空格隔開。
Sample Input

2
3

Sample Output

0 1
0 2 3

 

 

/*
**n條直線時，交點數情況存到arr[n]中。分成兩組，選任意一條A作為代表，與A平行的都在A組，其他的放到B組，
**則交點數為a * b + arr[b];
*/
#include 
bool arr[22][200];
//標記法某種程度上具備排序的性質
int main(){
	int n, a, b;
	arr[0][0] = arr[1][0] = 1;
	for(int i = 2; i < 21; ++i){
		arr[i][0] = 1; //0一定有，有則標記
		for(int j = 1; j < i; ++j){
			a = j; b = i - j;
			for(int k = 0; k <= (b-1) * b / 2; ++k)
				if(arr[b][k]) arr[i][a * b + k] = 1;				
		}
	}
	while(scanf("%d", &n) == 1){
		for(int i = 0; i <= (n-1) * n / 2; ++i)
			if(i == 0) printf("%d", i);
			else if(arr[n][i]) printf(" %d", i);
		printf("\n");
	}
	return 0;
}