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
#include <cstdio>
#include <vector>
#include <map>
#include <set>
using namespace std;

// -----------------------------------------

#define FOR(i,a,b) for(int (i)=(int)(a); (i)!=(int)(b); ++(i))

struct Mine {
    long long int X, R, left, right;
    long long int field_left, field_right;

    Mine(){}
};
typedef Mine *MinePtr;

// -----------------------------------------

int n;
vector<Mine> A;
map<long long int, MinePtr> M;

int main() {
    scanf("%d", &n); A.resize(n);
    FOR(i,0,n) {
        scanf("%lld %lld", &A[i].X, &A[i].R);
        A[i].left = A[i].X - A[i].R;
        A[i].right = A[i].X + A[i].R;
        M[A[i].X] = &A[i];
    }

    FOR(i,0,n) {
        long long L = A[i].left;
        long long R = A[i].right;

        while(true) {
            bool changed = false;
            for(map<long long int, MinePtr>::iterator it = M.lower_bound(L); it != M.end() && it->second->X <= R; ++it) {
                MinePtr b = it->second;
                if (L > b->left){ L = b->left; changed = true; }
                if (R < b->right){ R = b->right; changed = true; }
            }
            if (!changed) break;
        }

        A[i].field_left = L;
        A[i].field_right = R;
    }

    set<long long int> P;
    FOR(i,0,n) {
        P.insert(A[i].field_left);
        P.insert(A[i].field_right);
    }
    map<long long int, int> P_num;

    int pos = 0;
    for(set<long long int>::iterator it = P.begin(); it != P.end(); ++it) {
        P_num[*it] = pos;
        ++pos;
    }

    set<vector<bool> > S;
    FOR(x,0,1<<n) {
        vector<bool> result(P_num.size(), false);

        int y = x;
        FOR(i,0,n) {
            if (y%2) {
                int start_id = P_num.find(A[i].field_left)->second;
                int end_id = P_num.find(A[i].field_right)->second;
                FOR(j, start_id, end_id+1) result[j] = true;
            }
            y >>= 1;
        }

        S.insert(result);
    }

    printf("%d\n", S.size());
}