Overview

This problem requires finding the minimum number of cameras needed to photograph all shooting stars that move diagonally (in the upper-left direction) on a grid. At first glance, it appears to be a complex grid search problem, but by organizing it mathematically, it can be reduced to the very simple problem of “counting the number of distinct values.”

Analysis

Properties of Shooting Star Trajectories

The \(k\)-th shooting star starts at initial position \((R_k, C_k)\) and moves to cell \((R_k - t, C_k - t)\) at time \(t\) (\(t \geq 0\)). Let’s focus on the value “column number minus row number” of the cell where the shooting star is located.

\[(C_k - t) - (R_k - t) = C_k - R_k\]

This shows that the value is always the constant \(C_k - R_k\), independent of time \(t\). This means that each shooting star moves in the upper-left direction along a specific diagonal running from upper-left to lower-right.

Relationship with Different Diagonals

Shooting stars with different values of \(C_k - R_k\) (the difference between column and row numbers) move along different diagonals. These diagonals are parallel and never intersect on the grid. Therefore, it is impossible for a single camera to simultaneously photograph shooting stars moving along different diagonals. Thus, we can see that the number of cameras needed must be at least the number of diagonals on which shooting stars exist (the number of unique values of \(C_k - R_k\)).

Covering Stars on the Same Diagonal

Can shooting stars on the same diagonal always be photographed simultaneously by a single camera?

For example, suppose two shooting stars \(A, B\) on the same diagonal have initial positions \((R_A, C_A), (R_B, C_B)\) respectively, with \(R_A < R_B\) (\(A\) is more to the upper-left, \(B\) is more to the lower-right). Since shooting star \(B\) moves toward the upper-left, at time \(t = R_B - R_A\), it passes through exactly \((R_A, C_A)\), which is the initial position of \(A\). Therefore, if we place one camera at cell \((R_A, C_A)\), we can photograph both shooting star \(A\) (at time \(0\)) and shooting star \(B\) (at time \(R_B - R_A\)).

Generalizing this, among all shooting stars on the same diagonal, if we place one camera at the initial position of the one furthest to the “lower-right” (i.e., the one with the largest \(R_k\)), we can photograph all shooting stars on that diagonal.

Conclusion

From the above analysis, by placing exactly one camera per diagonal, we can cover all shooting stars on that diagonal. Therefore, the minimum number of cameras needed is exactly equal to the number of distinct values of \(C_k - R_k\) across all shooting stars (the count of unique values).

Algorithm

1. For each shooting star \(k = 1, 2, \ldots, N\), compute the value \(D_k = C_k - R_k\) and store it in an array.
2. Sort the stored array in ascending order.
3. Remove duplicate elements from the sorted array (make it unique).
4. Output the number of elements (size) of the deduplicated array.

Complexity

• Time Complexity: \(O(N \log N)\) Sorting the \(N\) elements is the bottleneck of the entire algorithm. Since \(N \le 2 \times 10^5\), this is sufficiently fast for the time limit.
• Space Complexity: \(O(N)\) \(O(N)\) memory is used for the array holding the \(C_k - R_k\) values for each shooting star.

Implementation Notes

• The grid dimensions \(H, W\) can be as large as \(10^9\), but since the number of shooting stars \(N\) is at most \(2 \times 10^5\), we only process the coordinate information of the shooting stars rather than storing the entire grid in memory.

• The value \(C_k - R_k\) can be negative, but this can be handled without issues by using a signed integer type (such as long long in C++).

• In C++, the standard technique for removing duplicates is to use std::sort followed by a combination of std::unique and erase, which provides a concise and efficient implementation.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long H, W;
    int N;
    if (!(cin >> H >> W >> N)) return 0;
    
    vector<long long> diffs(N);
    for (int i = 0; i < N; ++i) {
        long long r, c;
        cin >> r >> c;
        diffs[i] = c - r;
    }
    
    sort(diffs.begin(), diffs.end());
    diffs.erase(unique(diffs.begin(), diffs.end()), diffs.end());
    
    cout << diffs.size() << "\n";
    
    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.