USACO SILVER::2019 January - Mountain View

Mountain View

Point

Design(x)

Big O(time)

Big O(memory)

Code(x)

// https://beenpow.github.io/
#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define f first
#define s second
#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pair<int, int> >
typedef long long ll;
const int MAXN = 100000 + 10;
#define MOD 1000000007
using namespace std;

int n;
int cid[MAXN];
int x[MAXN], y[MAXN];
int pos[MAXN], neg[MAXN];
bool cmp(int i, int j){
    if(neg[i] == neg[j]) return pos[i] > pos[j];
    else return neg[i] < neg[j];
}
void process(){
    cin >> n;
    rep(i, 0, n){
        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 ans = 0;
    int mx = -1;
    rep(i, 0, n){
        if(pos[cid[i]] > mx){
            mx = pos[cid[i]];
            ans++;
        }
    }
    cout << ans << endl;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    process();
    return 0;
}