当前位置：首页 > article >正文

洛谷P2789 直线交点数

article 2025/2/6 21:34:43

题目传送门

直线交点数

题目描述

假设平面上有 $N$ 条直线，且无三线共点，那么这些直线有多少种可能的交点数？

输入格式

一行，一个整数 $N$ ，代表有 $N$ 条直线。

输出格式

一行，一个整数，表示方案总数。

样例 #1

样例输入 #1

样例输出 #1

提示

对于所有数据，满足 $\le N \le 25$ 。

题目分析：这道题的关键在于：我们认为线与线之间只存在平行或相交的关系，而不考虑具体位置，并且无三线共点。因此我们只需考虑直线之间是否平行还是相交，此题的目的是求交点方案数，如何求交点：

可以从简单的来推推看：

一条直线，必然只有一种方案
两条直线：两条直线平行， 0 个交点，两条直线相交， 1 个交点，两种方案
三条直线**（三种方案）**

具体分析一下 n=4 的情况：
4 条直线全部平行，则 0 交点个数 =4*(4-4)。
其中 3 条直线平行，则 3 交点个数 =3*(4-3) 。
其中 2 条直线平行，则这2条直线与另2条直线的交点数为4,而另2条直线之间可能有0个或1个交点（见 n=2 的情况,共 4 个交点或 5 个交点。个数 =2(4-2)+0 或 1*
4 条直线均不平行（可看成 1 条直线平行），这 1 条直线与其它 3 条直线的交点数为 3，而其它 3 条直线之间的交点数为 3，共 6 个交点。个数 =1(4-1)+3*
经过以上分析，我们可以得如下结论：
N条直线的交点方案=X 条平行线与（N-X）条直线交叉的交点数+（N-X）条直线本身的交点方案
=N*(N-X)+(N-X)条直线本身的交点方案（1<=X<=N）,在具体编程时，我们设置一个标志数组 f[0…max]，在使用上述结论递归求解的过程中，每得到一种交点数 k，则置 f[k]为 true（初始 f[0]~f[max]均为 false）。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 26;

bool f[1000];
int n,maxn = -1,ans;


void dfs(int n,int k)//
{
	if(n == 0)
	{
		f[k] = true;
		maxn = max(maxn,k);
	}
	for(int x = n; x >= 1; x --) dfs(n - x,x * (n - x) + k);//x表示平行线的数量，n - x表示直线数量（不相交的）
}

ll read()
{
	ll s=0,f=1;
	char ch=getchar();
	
	while (ch<'0'||ch>'9')
	{
   	   if (ch=='-') f=-1;
	   ch=getchar();
	}
	while (ch>='0'&&ch<='9')
	{
	   s=s*10+ch-'0';
	   ch=getchar();
	}
	return s*f;
}


int main() {
   
  
    n = read();
    
    dfs(n,0);
    
    for(int i = 0; i <= maxn; i++)
    {
    	if(f[i]) ans++;
	}
	
	cout<<ans;
	
    return 0;
}