直线交点数

题意

共有 n 条直线，允许平行且无三线共点。求可能出现多少种不同的交点总数。

思路

同一平行组内部没有交点，不同平行组的任意两线产生一个交点。令 possible[t] 是 t 条线能形成的所有交点数。

若最后加入 parallel 条互相平行的线，前面已有 t-parallel 条，新组和旧线产生 parallel*(t-parallel) 个新交点。因此把 possible[t-parallel] 中每个值加上这项并放入集合。

小规模状态如下：

直线数 `t`	`possible[t]`
`0`	`{0}`
`1`	`{0}`
`2`	`{0,1}`
`3`	`{0,2,3}`
`4`	`{0,3,4,5,6}`

所以 n=4 时有 5 种交点数。

Python 知识

每个 DP 状态直接用 set 保存并自动去除重复交点数。
set.update(generator) 把一整批转移结果加入当前状态。
[set() for ...] 保证每个位置拥有独立集合。
生成器只逐个产生转移值。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：集合去重和更新。
/home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：转移结果生成器。

代码

python

1
2
3
4
5
6
7
8
9
10
11n = int(input())
possible = [{0}] + [set() for _ in range(n)]

for total in range(1, n + 1):
    for parallel in range(1, total + 1):
        possible[total].update(
            intersections + parallel * (total - parallel)
            for intersections in possible[total - parallel]
        )

print(len(possible[n]))

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39/**
 * P2789 直线交点数
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

// possible[t] 表示 t 条直线可能产生的交点数集合
// 用布尔数组标记
bool possible[MAXN][MAXN * MAXN / 2 + 5];
int n;

int main() {
    scanf("%d", &n);
    possible[0][0] = true;
    for (int total = 1; total <= n; ++total) {
        // 枚举有 parallel 条直线相互平行（剩余 total-parallel 条不平行）
        for (int parallel = 1; parallel <= total; ++parallel) {
            int add = parallel * (total - parallel); // 平行组与非平行组的交点
            for (int i = 0; i <= (total - parallel) * (total - parallel - 1) / 2; ++i) {
                if (possible[total - parallel][i])
                    possible[total][i + add] = true;
            }
        }
    }
    int ans = 0;
    int max_intersections = n * (n - 1) / 2;
    for (int i = 0; i <= max_intersections; ++i)
        if (possible[n][i]) ++ans;
    printf("%d\n", ans);
    return 0;
}

复杂度

n<=25，按实际状态数记为 S，时间复杂度 $O(n^2S)$ ，空间复杂度 $O(nS)$ 。

总结

几何问题可转成平行组大小的整数划分；集合 DP 只关心能否得到某个交点数，天然适合去重。

目录

题意

思路

Python 知识

代码

复杂度

总结