题解分析

1. 线交点数量的理论范围 在平面上画$n$条直线，交点数量 $m$的取值范围是有一定规律的。当$n$条直线相互平行时，交点数$m=0$ ；当 n条直线两两相交且任意三条直线不共点时，交点数量达到最大值 C= n×(n−1)/2。同时，我们可以通过调整直线的平行关系来得到不同数量的交点。设 n条直线中，有 k组平行线，每组平行线的数量分别为a1,a2,⋯,ak且∑i=1kai≤n那么实际的交点数量m=C
2. 判断能否得到指定交点数量 我们可以通过枚举所有可能的平行线组合情况来判断是否能得到指定的交点数量m。
3. 计算平面最多被分成的部分数当 n条直线两两相交且任意三条直线不共点时，平面被分成的部分数 K有公式K=2n×(n+1)+1，并且这个最大分割数与交点数量无关，只与直线的数量 n有关。 #include #include

// 计算组合数 C(n, 2) int combination(int n) { return n * (n - 1) / 2; }

// 判断能否用 n 条线得到 m 个交点 bool canGetCrossings(int n, int m) { if (m > combination(n) || m < 0) return false; // 枚举所有可能的平行线组合 for (int i = 0; i <= n; ++i) { for (int j = 0; j <= n - i; ++j) { for (int k = 0; k <= n - i - j; ++k) { for (int l = 0; l <= n - i - j - k; ++l) { int sum = combination(n) - combination(i) - combination(j) - combination(k) - combination(l); if (sum == m) return true; } } } } return false; }

// 计算 n 条线最多能把平面分成的部分数 int maxPieces(int n) { return n * (n + 1) / 2 + 1; }

int main() { int n, m; int caseNum = 1; while (std::cin >> n >> m && (n != 0 || m != 0)) { if (canGetCrossings(n, m)) { int pieces = maxPieces(n); std::cout << "Case " << caseNum << ": " << n << " lines with exactly " << m << " crossings can cut the plane into " << pieces << " pieces at most." << std::endl; } else { std::cout << "Case " << caseNum << ": " << n << " lines cannot make exactly " << m << " crossings." << std::endl; } caseNum++; } return 0; }