出現した区画が \((r,c)\) である流れ星が位置する区画 \((x,y)\) について、\(x,y\) が満たす条件を考えます。

\((x,y)\) はある \(t\) について \((r-t,c-t)\) を満たします。よって、\(x-y\) は \(t\) によらず \(r-c\) と等しいです。

この考察から、\(R _ i-C _ i\ne R _ j-C _ j\) であるような \(2\) つの流れ星 \(i,j\) を \(1\) つのカメラで撮影することはできません。 逆に、\(R _ i-C _ i=R _ j-C _ j=d\) であるような \(2\) つの流れ星は、\((1+d,1)\) もしくは \((1,1-d)\) のどちらかの区画にカメラを設置することでどちらも撮影することができます。

よって、求めるカメラの最小個数は、\(R _ i-C _ i\) の種類数と等しいことがわかりました。

連想配列やソートを行うことによって \(O(N\log N)\) 時間でこの問題を解くことができます。

実装例は以下のようになります。

#include <iostream>
#include <set>
using namespace std;

int main() {
    int H, W, N;
    cin >> H >> W >> N;

    set<int> camera; // それぞれのカメラに対応する R - C の値を管理する集合
    for (int i = 0; i < N; ++i) {
        int r, c;
        cin >> r >> c;
        camera.emplace(r - c); // 集合に R - C を追加
    }
    cout << size(camera) << endl; // R - C の種類数が答え
    return 0;
}

H, W, N = map(int, input().split())

camera = set() # それぞれのカメラに対応する R - C の値を管理する集合
for i in range(N):
    r, c = map(int, input().split())
    camera.add(r - c) # 集合に R - C を追加

print(len(camera)) # R - C の種類数が答え