C++ Practice Problem – Calculating the Number of Intersection Points of Lines

Time Limit: 2s Memory Limit: 192MB

Problem Description

There are n lines on a plane, and no three lines intersect at a single point. How many different intersection points can these lines have?

For example, if n=2, the possible number of intersection points is 0 (parallel) or 1 (not parallel).

Input Format

The input consists of multiple test cases, each occupying one line, with each line containing a positive integer n (n<=20), where n represents the number of lines.

Output Format

For each test case, output one line listing all possible intersection counts in ascending order, with each number separated by a space.

Sample Input

2

3

Sample Output

0 1

0 2 3

Code

#include <iostream>#include <vector>#include <algorithm>using namespace std;
int main() {    int n;
    // dp[i] represents all possible intersection counts for i lines    vector<vector<bool>> dp(21, vector<bool>(200, false));
    // Initialization    for (int i = 0; i <= 20; i++) {        dp[i][0] = true;  // All lines are parallel    }
    // Dynamic Programming    for (int i = 1; i <= 20; i++) {        for (int j = 1; j <= i; j++) {  // j lines are not parallel to the new line            int k = i - j;  // k lines are parallel to the new line            int add = j * k;  // New intersection count
            for (int x = 0; x < 200; x++) {                if (x + add < 200 && dp[j][x]) {                    dp[i][x + add] = true;                }            }        }    }
    // Handle input and output    while (cin >> n) {        vector<int> result;        for (int j = 0; j < 200; j++) {            if (dp[n][j]) {                result.push_back(j);            }        }
        // Sort and output        sort(result.begin(), result.end());        for (int i = 0; i < result.size(); i++) {            if (i > 0) cout << " ";            cout << result[i];        }        cout << endl;    }
    return 0;}

Output ResultAlgorithm Explanation

1. State Definition：<span>dp[i][j]</span> indicates whether i lines can form j intersection points

2. State Transition：

• Divide i lines into two groups: k parallel lines, j lines that intersect with all others

• New intersection count = number of parallel lines × number of lines intersecting with others

• That is:<span>dp[i][x + k*(i-k)] |= dp[i-k][x]</span>

Initialization：0 lines have 0 intersection points

Problem Analysis

For n lines, with no three lines intersecting at a point, the possible range of intersection counts is:

• Minimum: 0 (all lines are parallel)

• Maximum: n(n-1)/2 (all lines intersect pairwise)

Key Point:The number of intersection points depends on the parallel relationship of the lines.

Understanding the Project

Let <span>dp[i][j]</span> indicate whether i lines can form j intersection points.

When adding the i-th line:

• If it is parallel to the previous i-1 lines, the number of intersection points remains unchanged

• If it is parallel to k previous lines and intersects with the remaining i-1-k lines, it adds (i-1-k) intersection points

Thus, the state transition is:

dp[i][j] = dp[i][j] || dp[k][j - (i-1-k)*k]

where k ranges from 0 to i-1, indicating the number of lines parallel to the i-th line (including itself)

Example Verification

n=2：

• 2 parallel lines: 0 intersection points

• 2 intersecting lines: 1 intersection point

• Output: 0 1

n=3：

• 3 parallel lines: 0 intersection points

• 2 parallel, 1 intersecting: 2 intersection points

• 3 lines intersecting pairwise: 3 intersection points

• Output: 0 2 3

This solution can correctly handle all cases for n≤20.

C++ Basic Tutorial Collection

C++ Basic Materials

1. C++ Output

2. C++ Variables

3. C++ Input

4. C++ Expressions

5. IF Statements

6. IF Applications

7. WHILE Loops

8. FOR Loops

9. Arrays

10. One-Dimensional Arrays

11. Two-Dimensional Arrays

12. C++ Functions

13. C++ File Operations – Writing Files

If you find it interesting, please click on me