Overview

This problem involves treating the trajectories of shooting stars moving on a grid as “intervals” and covering them with the minimum number of cameras (points).

Since the movement direction of shooting stars is restricted to the upper-left (both row and column decrease), only shooting stars on the same diagonal can have overlapping paths. Therefore, by dividing the problem by diagonals and applying the classic “interval covering problem (greedy method)” to each, we can efficiently find the optimal solution.

---

Analysis

1. Dividing the grid into independent groups by diagonal

Shooting star \(k\) is located at cell \((R_k - t, C_k - t)\) at time \(t\). Focusing on the difference between the column number and row number: $\((C_k - t) - (R_k - t) = C_k - R_k\)\( This means that **the difference "column number - row number" remains constant** regardless of the change in time \)t$.

This implies that a shooting star moves along the same diagonal (a line with slope \(1\)). Shooting stars with different values of “column number - row number” (let’s call this \(d\)) will never have intersecting trajectories. Therefore, we can independently determine the minimum number of cameras for each group of shooting stars sharing the same \(d\), and sum up the results.

2. Representing shooting star movement as “intervals”

Consider a shooting star \(k\) on diagonal \(d\). The position on this diagonal can be represented one-dimensionally using only the row number \(r\) (since the column number is automatically determined as \(c = r + d\)).

The initial row number of shooting star \(k\) is \(R_k\). The shooting star moves toward the upper-left (decreasing row number) and disappears when it reaches the edge of the grid (when the row number becomes \(1\) or the column number becomes \(1\)). Let \(L_k\) be the row number just before disappearing. Then the range of row numbers where shooting star \(k\) exists can be expressed as the closed interval \([L_k, R_k]\).

\(L_k\) can be determined as follows: - To remain within the grid, the row number must satisfy \(r \geq 1\), and the column number must satisfy \(c = r + d \geq 1 \iff r \geq 1 - d\). - Therefore, the row number at the furthest upper-left position \(L_k\) is \(\max(1, 1 - d)\). - When \(d \geq 0\): \(L_k = 1\) - When \(d < 0\): \(L_k = 1 - d\)

With this, each shooting star can be represented as “interval \([L_k, R_k]\) on diagonal \(d\)”.

3. Reduction to the interval covering problem

On each diagonal, to photograph all shooting stars (intervals), we need to select some row numbers (camera positions) such that every interval \([L_k, R_k]\) contains at least one of the selected row numbers.

This is exactly the classic “interval covering problem” in competitive programming.

---

Algorithm

For each diagonal group, apply the following greedy method:

1. Sort all intervals \([L_k, R_k]\) in the group in ascending order of the right endpoint \(R_k\).
2. Process the sorted intervals from left to right.
3. If the current interval \([L_k, R_k]\) is not covered by the last placed camera (whose position is last), i.e., when \(L_k > \text{last}\):
   • A new camera needs to be placed.
   • At this point, placing the camera as far to the right as possible makes it easier to cover future intervals, so placing the camera at the right endpoint \(R_k\) of the current interval is optimal.
   • Update last to \(R_k\) and increment the camera count by \(1\).
4. Repeat this until all intervals have been processed.

---

Complexity

Time Complexity: \(O(N \log N)\)

• Grouping shooting stars by diagonal takes \(O(N)\) time.
• Let \(N_g\) be the number of elements in each group \(g\). Sorting within a group takes \(O(N_g \log N_g)\) time.
• The total sorting time is \(\sum O(N_g \log N_g) \leq O(N \log N)\).
• The greedy traversal takes \(O(N_g)\) for each group, and \(O(N)\) in total.
• Therefore, the overall time complexity is \(O(N \log N)\), which is well within the time limit.

Space Complexity: \(O(N)\)

• Storing information for each shooting star by group requires at most \(O(N)\) memory.
• Although the grid size \(H, W\) can be as large as \(10^9\), we do not use arrays to store the entire grid, so the space complexity is bounded by \(O(N)\).

---

Implementation Notes

• Handling huge coordinates: Since \(H, W \leq 10^9\), it is impossible to represent the grid with a two-dimensional array. We extract only the coordinates where shooting stars exist and group them by diagonal using an associative array (defaultdict in Python).

• Fast I/O: When processing input of scale \(N = 2 \times 10^5\) in Python, repeatedly calling input() may result in a Time Limit Exceeded (TLE). By reading all input at once using sys.stdin.read().split(), we can process the input efficiently.

  Source Code

import sys
from collections import defaultdict

def solve():
    # すべての入力を一度に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    H = int(input_data[0])
    W = int(input_data[1])
    N = int(input_data[2])
    
    # 高速化のため、スライスを用いて座標リストを構築
    R = [int(x) for x in input_data[3::2]]
    C = [int(x) for x in input_data[4::2]]
    
    # 対角線ごとにグループ分けを行う
    groups = defaultdict(list)
    for i in range(N):
        r = R[i]
        c = C[i]
        d = c - r
        l = 1 - d if d < 0 else 1
        groups[d].append((r, l))
        
    ans = 0
    # 各グループ（対角線）ごとに独立に区間カバー問題を解く
    for intervals in groups.values():
        # 右端 r の昇順にソート
        intervals.sort()
        last = -1
        for r, l in intervals:
            if l > last:
                ans += 1
                last = r
                
    print(ans)

if __name__ == '__main__':
    solve()

---

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