直线交点数计算

灵犀互娱笔试第五题，出自HDU
http://acm.hdu.edu.cn/showproblem.php?pid=1466

假设平面上有n条直线，且不存在三条或以上直线共点的情况，求这n条直线可能存在多少种不同交点数.
例n=2,则可能的交点数量为0(平行)或者1(不平行)。

Input

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

Output

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

动态规划
状态表示 f[i][j]表示i条直线，j个交点是否存在。
集合划分 m条直线的交点数 = (m - r)条平行线与r条直线交叉的交点数 + r条直线本身交点数 = (m - r) * r + r条直线本身交点数
只要f[i][j] = 1，那f[i][(i - r) * r + j] = 1;

#include <iostream>
#include <vector> 
using namespace std;

int main()
{
	string line;
	vector<int> a;
	while (getline(cin, line)) {
		a.push_back(stoi(line));
	}
	
	for (int i = 0; i < a.size(); i++) {
		int n = a[i];
		vector<vector<int>> f(25, vector<int> (200)); // 20条直线最多190个交点 
		f[0][0] = f[1][0] = 1;
		for (int i = 2; i <= n; i++) {
			f[i][0] = 1;
			for (int j = 0; j < i; j++) {
				for (int k = 0; k <= n * (n - 1) / 2; k++) {
					int b = i - j - 1;
					if (f[b][k] == 1) {
						f[i][(i - b) * b + k] = 1;
					}
				} 
			}
		} 
		
		for (int j = 0; j <= n * (n - 1) / 2; j++) {
			if (f[n][j] == 1) {
				cout << j << " ";
			} 
		}
		cout << endl;
	}
	
	return 0;
}