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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifdef LOCAL
#define debug(...) __VA_ARGS__
#else
#define debug(...) {}
#endif

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    debug(freopen("small11.in","r",stdin););
    int i;
    int n;
    cin>>n;
    pair<ll,ll> tab[n];
    for (i = 0; i < n; i++){
        ll a,b;
        cin>>a>>b;
        tab[i] = {a,b};
    }
    bool wy[(1<<n)];
    for (i = 0; i < (1<<n); i++) wy[i] = 0;
    for (i = 0; i < (1<<n); i++){
        bool vis[n];
        for (int j = 0; j < n; j++) vis[j] = 0;
        for (int j = 0; j < n ; j++){
            if (vis[j] || !(i&(1<<j))) continue;
            ll maksl = tab[j].first-tab[j].second;
            ll maksp = tab[j].first+tab[j].second;
            //cout<<"FOR "<<j<<" "<<maksl<<" "<<maksp<<"\n";
            int l = j-1;
            int p = j+1;
            vis[j] = 1;
            while ((l > -1) || (p <= n)){
                //if (l == -1) cout<<-2137<<" ";
              // else cout<<tab[l].first<<" ";
                //cout<<tab[p].first<<" "<<maksl<<" "<<maksp<<"\n";
                if (l > -1){
                    if (vis[l] || tab[l].first < maksl){
                        if (p > n || tab[p].first > maksp) break;
                    }else{
                        vis[l] = 1;
                        maksl = min(maksl,tab[l].first-tab[l].second);
                        maksp = max(maksp, tab[l].first+tab[l].second);
                        l--;
                    }
                }
                if (p <= n){
                   // cout<<p<<" "<<tab[p].first<<" "<<vis[p]<<"\n";
                    if (tab[p].first > maksp || vis[p]){
                        if (l < 0 || vis[l] || tab[l].first < maksl) break;
                    }else{
                        vis[p] = 1;
                        maksl = min(maksl,tab[p].first+tab[p].second);
                        maksp = max(maksp, tab[p].first+tab[p].second);
                        p++;
                    }
                }
            }
        }
        int maskwy = 0;
        for (int j = 0; j < n; j++) if (vis[j]) maskwy += (1<<j);
        wy[maskwy] = 1;
    }
    int wynik = 0;
    for (i = 0; i < (1<<n); i++) if (wy[i]) wynik++;
    cout<<wynik<<"\n";
    return 0;
}