洛谷P2789直线交点数问题终极解析：从递归到优化的完整指南

问题描述

洛谷P2789题目要求计算n条直线在平面上所有可能的交点数。这是一个经典的组合数学问题，考察的是对平行线关系的理解以及递归算法的应用能力。

算法核心思想

1. 平行线性质

• 一组平行线之间不会产生任何交点

• 不同组平行线之间会产生i*j个交点（i和j分别为两组平行线的数量）

2. 递归搜索策略

采用深度优先搜索(DFS)递归枚举所有可能的平行线分组方案：

1. 将n条直线划分为若干平行线组

2. 计算不同组之间的交点数

3. 累加所有可能的交点数组合

完整代码实现

#include <iostream>
#include <algorithm>

// 全局变量
int sum = 0;          // 总交点数之和
int p, n, r;          // p为剩余线数，n为总直线数，r为平行线数
bool A[100000] = {0}; // A[i]=1表示i个交点已存在，避免重复统计

// 递归函数：计算交点数
// p：剩余线数（当前待处理的线数）
// m：当前已计算的交点数
void plan(int p, int m) {
    // 终止条件：当剩余线数为0时，记录当前交点数
    if (p == 0) {
        if (A[m] == 0) { // 若该交点数未出现过，计入sum
            sum++;
        }
        A[m] = 1; // 标记为已存在
    } else {
        // 枚举平行线数量r（从p到1）
        for (int r = p; r >= 1; r--) {
            // 计算r条平行线与剩余p-r条线的交点数：r*(p-r)
            int newM = m + r * (p - r);
            // 递归处理剩余p-r条线
            plan(p - r, newM);
        }
    }
}

int main() {
    std::cin >> n; // 输入总直线数n
    plan(n, 0);    // 从n条线开始递归，初始交点数为0
    std::cout << sum << std::endl; // 输出总交点数之和
    return 0;
}

时间复杂度分析

• 最坏情况时间复杂度：O(2^n)

• 实际运行效率：对于n≤25的数据范围完全适用

算法优化空间

1. 记忆化搜索优化

2. 动态规划解法

3. 数学公式推导优化

应用场景延伸

1. 计算几何问题

2. 组合数学问题

3. 图形学中的碰撞检测