算法
(坐标压缩/离散化) $O(N\log N)$
$x$ 坐标和 $y$ 坐标相互独立,我们可以分别对这两个坐标进行坐标压缩。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::map;
using std::vector;
vector<int> compress(vector<int> a) {
int n = a.size();
map<int, int> mp;
rep(i, n) mp[a[i]] = 0;
int id = 1;
for (auto& p : mp) p.second = id++;
rep(i, n) a[i] = mp[a[i]];
return a;
}
int main() {
int h, w, n;
cin >> h >> w >> n;
vector<int> a(n), b(n);
rep(i, n) cin >> a[i] >> b[i];
a = compress(a);
b = compress(b);
rep(i, n) {
cout << a[i] << " " << b[i] << '\n';
}
return 0;
}