计算直线的交点数

coding>C++
645 词

题目描述

平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。
比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。

输入

输入数据包含多个测试实例,每个测试实例占一行,每行包含一个正整数n（n<=20）,n表示直线的数量.

输出

每个测试实例对应一行输出，从小到大列出所有相交方案，其中每个数为可能的交点数,每行的整数之间用一个空格隔开。

样例输入

1
2
2
3

样例输出

1
2
0 1
0 2 3

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include <cstring>
using namespace std;
int main() {
    int dp[21][200];
    int n;
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < 21; i++) {
        dp[i][0] = 1;
        for (int j = 0; j <= i * (i - 1) / 2; j++)
            if (dp[i][j] == 1)
                for (int r = i + 1; r < 21; r++)
                    dp[r][(r - i) * i + j] = 1;
    }
    while (cin >> n) {
        for (int i = 0; i <= n * (n - 1) / 2; i++)
            if (dp[n][i] == 1) cout << i<<" ";
        cout << endl;
    }
    return 0;
}