首先,答案最小为 (n+1)。
注意到圆与圆之间互不相交,因此只有圆的直径上被小圆全部覆盖答案才会 (+1)。
如何判断这一情况?
首先可以将坐标离散化,然后按半径大小从小到大加入圆(因为半径大的圆只会被半径比它小的圆覆盖直径),用线段树维护即可。
由于我们维护的是线段之间的关系,因此加入直径时左端点要 (+1)。
#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d
", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)
#define DC int T = gi <int> (); while (T--)
using namespace std;
typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;
template <typename T>
inline T gi()
{
T f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
const int INF = 0x3f3f3f3f, N = 600003, M = N << 1;
int n;
struct Circle
{
int l, r, bj;
} a[N];
int b[N];
inline bool cmp(Circle x, Circle y)
{
return x.bj < y.bj;
}
namespace SGT
{
bool tr[N << 2];
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
void pushup(int p) {tr[p] = tr[ls(p)] & tr[rs(p)];}
void pushdown(int p) {tr[ls(p)] |= tr[p], tr[rs(p)] |= tr[p];}
void modify(int ql, int qr, int l, int r, int p)
{
if (ql <= l && r <= qr) {tr[p] = 1; return;}
pushdown(p);
int mid = (l + r) >> 1;
if (ql <= mid) modify(ql, qr, l, mid, ls(p));
if (qr > mid) modify(ql, qr, mid + 1, r, rs(p));
pushup(p);
return ;
}
bool query(int ql, int qr, int l, int r, int p)
{
if (ql <= l && r <= qr) return tr[p];
pushdown(p);
int mid = (l + r) >> 1;
bool ans = 1;
if (ql <= mid) ans = query(ql, qr, l, mid, ls(p));
if (qr > mid) ans &= query(ql, qr, mid + 1, r, rs(p));
return ans;
}
} //namespace SGT
int main()
{
// File("");
n = gi <int> ();
for (int i = 1; i <= n; i+=1)
{
int x = gi <int> (), r = gi <int> ();
a[i] = (Circle){x - r, x + r, r};
b[i * 2 - 1] = x - r, b[i * 2] = x + r;
}
sort(b + 1, b + 1 + n * 2);
int tot = unique(b + 1, b + 1 + n * 2) - b - 1;
for (int i = 1; i <= n; i+=1)
a[i].l = lower_bound(b + 1, b + 1 + tot, a[i].l) - b, a[i].r = lower_bound(b + 1, b + 1 + tot, a[i].r) - b;
sort(a + 1, a + 1 + n, cmp);
int ans = n + 1;
for (int i = 1; i <= n; i+=1)
{
bool all1 = SGT :: query(a[i].l + 1, a[i].r, 1, n * 2, 1);
if (all1) ++ans;
SGT :: modify(a[i].l + 1, a[i].r, 1, n * 2, 1);
}
printf("%d
", ans);
return 0;
}