1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for (int i = (a); i <= (b); ++i)
#define FOR(i,n) REP(i,0,int(n)-1)
#define MAXN 300007
#define MOD 1000 * 1000 * 1000 + 7
typedef long long ll;
int n;
ll position[MAXN], range[MAXN], res;

// From EPFL/UWr library:
struct MinTree {
int* el, s;
MinTree (int h) { // domain of elements is [0..2^h-1]
el = new int[2*(s = 1<<h)];
FOR(x,2*s) el[x] = MAXN+7; // maybe you want 0 here?
}
~MinTree() { delete [] el; }
void Set (int p, int v) { // watch out: will overwrite a smaller value
for (p += s, el[p] = v, p /= 2; p > 0; p /= 2) el[p] = min(el[2*p],el[2*p+1]);
}
int Find (int p, int k) { // min on segment [p,k]
int m = MAXN+7; p += s; k += s;
while (p < k) {
if (p&1) m = min(m, el[p++]);
if (!(k&1)) m = min(m, el[k--]);
p /= 2; k /= 2;
}
if (p == k) m = min(m, el[p]);
return m;
}
};

MinTree lleft(19), rright(19);
pair<int, int> directly[MAXN], current_range;
pair<ll, int> lengths[MAXN];
vector<int> taken;

void backtrack(int i){
  if (i == n){
    res++;
    return;
  }

  taken.push_back(lengths[i].second);
  backtrack(i+1);
  taken.pop_back();
  for(int j = 0; j < taken.size(); j++){
    if (directly[taken[j]].first <= directly[lengths[i].second].first &&
        directly[lengths[i].second].second <= directly[taken[j]].second){
      return;
    }
  }
  backtrack(i+1);
}

int main(){
  scanf("%d", &n);

  for(int i=0;i<n;i++){
    scanf("%lld%lld",&position[i], &range[i]);
  }

  for(int i = 0; i< n;i++){
    directly[i].first = lower_bound(position, position+n, position[i]-range[i]) - position;
    directly[i].second = upper_bound(position, position + n, position[i]+range[i]) - position - 1;
    lleft.Set(i, directly[i].first);
    rright.Set(i, -directly[i].second);
  }

  for(int i = 0; i < n; i++){
    current_range = make_pair(lleft.Find(directly[i].first, directly[i].second),
        -rright.Find(directly[i].first, directly[i].second));
    if (directly[i] != current_range){
      directly[i] = current_range;
      lleft.Set(i, directly[i].first);
      rright.Set(i, -directly[i].second);
      i--;
    }
  }

  sort(directly, directly+n);
  n = unique(directly, directly+n) - directly;
  for(int i = 0; i < n; i++){
    lengths[i] = make_pair(directly[i].first - directly[i].second, i);
  }
  sort(lengths, lengths + n);
  backtrack(0);

  printf("%lld\n", res);
}