题目描述

Czy找到宝藏获得屠龙宝刀和神秘秘籍！现在他要去找经常ntr他的Jmars报仇……

Czy学会了一招“堕天一击”，他对一个地点发动堕天一击，地面上就会留下一个很大的圆坑。圆坑的周围一圈能量太过庞大，因此无法通过。所以每次czy发动技能都会把地面分割。Jmars拥有好大好大的土地，几十眼都望不到头，所以可以假设土地的大小是无限大。现在czy对他发动了猛烈的攻击，他想知道在泽宇攻击之后他的土地被切成几份了?

Czy毕竟很虚，因此圆心都在x坐标轴上。另外，保证所有圆两两之间不会相交。

 

输入

输入第一行为整数n，表示czy放了n次堕天一击。

接下来n行，每行两个整数x[i]，r[i]。表示在坐标（x[i] , 0）放了一次堕天一击，半径为r[i]。

 

输出

输出一行，表示地面被分割成几块。

 

样例输入

47 5-9 1111 90 20

 

样例输出

6 【题解】 A掉了~但是是因为题水啊。虽然我讲了一下但是大概大佬们在我讲之前已经懂了= =。

复习一下数学高考知识（虽然众所周知的我数学偏科）：圆与圆之间的五种位置关系：相交、内切、外切、相离、内含。第一种题目里排除了，剩下的所有情况正常情况下都是多一个圆就多一个区域。我还多考虑了一下重复的圆，不过不知道有没有这种数据。加上剩下的无限大土地，就是以不重复的圆的数目+1为基准。至于多出来的，都是因为有圆被多个圆内切，整个把圆切成了两半。    先把圆排序，按左边界从小到大、左边界相同的右边界从大到小，这样排主要是为了保证能内切本圆的圆都在它后面。枚举各个圆，肯定要O(n)的效率，只能尽量优化一下判断部分。刚开始想用类似单调队列的办法，发现也不是那么容易维护，就在每个点建了个堆，堆顶是目前这个圆内部最靠右的圆的右边界。这个合理性好像是可以证？因为不相交所以它就合理了，如果有圆相切它一定左边界连着堆顶。     听了ryf大佬讲题发现堆并不是那么重要，直接删掉它并没有什么关系，拿个变量维护一下就好了。大佬们讲得非常精彩。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int sj=300010;int n,jg;struct ci{    int x,r,zj,yj;    bool cf;}c[sj];int mp(const ci&a,const ci&b){    if(a.cf!=b.cf) return a.cf
         
          b.yj;    return a.zj
          
           =c[i].yj||c[j].zj!=a) break; if(c[j].yj>a) a=c[j].yj; if(a==c[i].yj) { jg++; break; } } } printf("%d",jg); return 0;}