http://blog.csdn.net/firenet1/article/details/47041145
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cmath>
#include <cstdio>
#include <set>
using namespace std;
const int maxn=;
struct Circle
{
int id,x,y,r;
Circle(int cid=,int cx=,int cy=,int cr=)
{
id=cid; x=cx; y=cy; r=cr;
}
}cir[maxn],P[maxn]; bool cmp(Circle a, Circle b)
{
return a.x<b.x;
}
int globalx;
struct point{
int id,ty;
point(int cid=, int cty=){
id=cid;
ty=cty;
}
};
double yposition(int id, int ty)
{
double x=globalx-cir[id].x;
double y=sqrt(1.0*cir[id].r*cir[id].r-x*x);
if(ty==)return cir[id].y+y;
return cir[id].y-y;
}
bool operator <(point a, point b)
{
if(a.id==b.id)return a.ty>b.ty;
return yposition(a.id,a.ty)>yposition(b.id,b.ty);
}
bool operator == (point a, point b)
{
return a.id==b.id&&a.ty==b.ty;
} set<point>Q;
int dep[maxn];
int main()
{
int n;
while(scanf("%d",&n)==)
{
Q.clear();
int cnt=;
for(int i=; i<n; i++)
{
scanf("%d%d%d",&cir[i].x,&cir[i].y, &cir[i].r);
cir[i].id=i;
P[cnt++]=Circle(i,cir[i].x-cir[i].r,);
P[cnt++]=Circle(i,cir[i].x+cir[i].r,);
}
sort(P,P+cnt,cmp);
memset(dep,,sizeof(dep));
set<point>:: iterator it1,it2;
int ans=;
for(int i=; i<cnt; i++)
{
globalx=P[i].x;
if(P[i].y==)
{
Q.erase(point(P[i].id,));
Q.erase(point(P[i].id,));
}else
{
it1=Q.insert(point(P[i].id,)).first;
it2=it1;
it1++;
if(it1==Q.end()||it2==Q.begin()){
dep[ P[i].id] =;
}else
{
it2--;
if(it1->id==it2->id){
dep[P[i].id]=dep[it1->id]+;
}else
{
dep[P[i].id]=max(dep[it1->id],dep[it2->id]);
}
} Q.insert(point(P[i].id,)); }
ans=max(dep[P[i].id],ans);
}
printf("%d\n",ans);
}
return ;
}