直线交点数
题目描述
假设平面上有 N N N 条直线,且无三线共点,那么这些直线有多少种可能的交点数?
输入格式
一行,一个整数 N N N,代表有 N N N 条直线。
输出格式
一行,一个整数,表示方案总数。
样例 #1
样例输入 #1
4
样例输出 #1
5
提示
对于所有数据,满足 1 ≤ N ≤ 25 1 \le N \le 25 1≤N≤25。
问题链接: P2789 直线交点数
问题分析: 数学问题,不解释。
参考链接: (略)
题记: (略)
AC的C++语言程序如下:
/* P2789 直线交点数 */
#include <iostream>
using namespace std;
const int N = 25 + 1;
bool f[N * N] = {
false};
int ans = 0;
void dfs(int p, int m)
{
if (p == 0) {
if (f[m] == false) ans++;
f[m] = true;
} else
for (int i = p; i >= 1; i--)
dfs(p - i, i * (p - i) + m);
}
int main()
{
int n;
cin >> n;
dfs(n, 0);
cout << ans;
}
文章评论