The key observation is that mountain $i$ is occluded by mountain $j$ (i.e. its peak is lies on the shape of mountain $j$) if and only if $x_i - y_i \geq x_j - y_j$ and $x_i + y_i \leq x_j + y_j$: that is, the base of mountain $i$ (the interval $[x_i-y_i, x_i + y_i]$) is contained in the base of mountain $j$.

First suppose for simplicity that every $x_i - y_i$ is distinct. Then if we sort the mountains in increasing order by $x_i - y_i$, a mountain is occluded if and only if for every previous mountain $j$, the inequality $x_j + y_j < x_i + y_i$ holds. This is because the previous mountains are exactly the mountains $j$ for which $x_j - y_j < x_i - y_i$. So as we sweep through the sorted list of mountains, we can keep track of the largest value of $x_j + y_j$ seen so far, and use this to determine whether each new mountain in the list is occluded or visible.

The same idea works even if not all $x_i - y_i$ are distinct, but we need to be careful about how we break ties when sorting. For two mountains $i$ and $j$ with $x_i - y_i = x_j - y_j$ and, say, $x_i + y_i < x_j + y_j$, we want mountain $j$ to appear before mountain $i$ in the sorted list, since $i$ is occluded by $j$ but not vice versa.

The following code implements the above algorithm:

#include <iostream> #include <algorithm> using namespace std; #define MAXN 100000 int N; int x[MAXN], y[MAXN]; int pos[MAXN], neg[MAXN]; int cid[MAXN]; bool cmp(int a,int b) { if(neg[a] == neg[b]) return pos[a] > pos[b]; return neg[a] < neg[b]; } int main() { cin >> N; for(int i=0;i<N;i++) { cin >> x[i] >> y[i]; pos[i] = x[i]+y[i], neg[i] = x[i]-y[i]; cid[i] = i; } sort(cid,cid+N,cmp); int mxpos = -1; int ans = 0; for(int i=0;i<N;i++) { if(pos[cid[i]] > mxpos) { ans++; mxpos = pos[cid[i]]; } } cout << ans << '\n'; }