vijos p1883

题意：

有些东西就如同月光的魔法一般.

Luke是爱着vijos的.
他想为自己心爱的东西画些什么.

就画N个圆吧.
把它们的圆心都固定在x轴上.

圆与圆.
为了爱,两两不能相交.
为了爱,它们可以互相贴在一起.
内切或外切,都是允许的.

vijos的美丽,在于人心.
vijos的孩子们,一定能告诉大家:Luke画的圆究竟把平面分割成了多少块?

月光恬美地洒在大地上.
Luke知道,如果什么都不画,平面就只有一块.多美呢!
Luke知道,只画一个圆,平面就分成了两块.也很美呢!
但Luke还是要多画一些的,因为他真的深爱着vijos呢.

找出完全包含而又最大的圆
然后按左端点递增，左端点相同则右端点越远越优先排序
每个圆本来只能增加1个平面
会出现更多是因为一些圆首尾相接把一个大圆割成了两部分
那我们只要找出每个圆的一级祖先就可以判断了
然后求每个圆的一级祖先可以用我在程序中的dfs来求出，正确性应该显然。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #include<map>
 8 using namespace std;
 9 #define MOD 1000000007
10 const int INF=0x3f3f3f3f;
11 const double eps=1e-5;
12 typedef long long ll;
13 #define cl(a) memset(a,0,sizeof(a))
14 #define ts printf("*****
");
15 const int MAXN=300010;
16 int n,m,tt;
17 struct Node
18 {
19     int l,r,fa;
20     int sum;
21 }c[MAXN];
22 int now;
23 bool cmp(Node a,Node b)
24 {
25     if(a.l==b.l)
26         return a.r>b.r;
27     else return a.l<b.l;
28 }
29 void dfs(int R)
30 {
31     while(now<=n&&c[now].r<=c[R].r)
32     {
33         c[now].fa=R;
34         now++;
35         dfs(now-1);
36     }
37     return;
38 }
39 int main()
40 {
41     int i,j,k;
42     while(~scanf("%d",&n))
43     {
44         int o,r;
45         for(i=1;i<=n;i++)
46         {
47             scanf("%d%d",&o,&r);
48             c[i].l=o-r;
49             c[i].r=o+r;
50             c[i].sum=0;
51         }
52         sort(c+1,c+n+1,cmp);
53         c[0].r=2147483647;
54         now=1;
55         dfs(0);
56         int ans=n+1;
57         for(i=1;i<=n;i++)
58         {
59             c[c[i].fa].sum+=c[i].r-c[i].l;
60         }
61         for(i=1;i<=n;i++)
62         {
63             if(c[i].sum==c[i].r-c[i].l) ans++;
64         }
65         printf("%d
",ans);
66     }
67     return 0;
68 }