HDU 1466 计算直线的交点数

问题：求n根直线所组成的所有交点数。

分析：前3根直线都很好分析，很容易理解，所以我们从第三根再增加一根到第四根来分析，这里能包含后面的所有情况
当n=4时：

1.四条直线全部平行，无交点2.其中三条平行，交点数: (n-1)*1 +0=3；3.其中两条平行，而另外两条直线的交点既可能平行也可能相交，因此交点数据分别为： (n-2)*2+0=4，(n-2)*2+1=54. 四条直线互不平行，交点数为(n-3)*3+3条直线的相交情况： (n-3)*3+0=3 ，(n-3)*3+2=5 ，(n-3)*3+3=6
发现：M条直线的交点方案数 = r 条直线交叉的交点数与(m-r)条平行线 + r 条直线本身的交点方案 = (m - r) * r + r 条直线之间的交点数。AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int dp[21][202];

int main()
{
    int n,i,j;
    memset(dp,0,sizeof(dp));
    for(i = 0; i < 21; i++)
    {
        dp[i][0] = 1;      //1标记第i根线存在j(0)个点这种可能
    }
    for(n = 2; n < 21; n++)
    {
        for(i = 1; i < n; i++)
        {
            for(j = 0; j < 201; j++)
            {
                if(dp[n-i][j] == 1)  //如果n-i根线时存在j个点
                {
                    dp[n][j+i*(n-i)] = 1;
                }
            }
        }
    }
    while(scanf("%d",&n)!=EOF)
    {
        printf("0");  //所有的都有0个交点
        for(i = 1; i < 201; i++)
        {
            if(dp[n][i] == 1)
            {
                printf(" %d",i);
            }
        }
        printf("\n");
    }

    return 0;
}

补充：软件开发 , C++ ,