说白了，就是这个样子：
这个玩意明显是一个优美的树形结构
是个森林
然后建个虚点0，并且w[0]=0，然后树形dp即可
f[x]=max(w[x],∑f[son])
难点是：树怎么建？
就要上计算几何了：
如果我们用扫描线扫过去
发现，同时存在的两个圆，由于不相交，不相切，所以 相对位置始终保持不变
或者说，不论扫到哪个位置，两个圆的四个纵坐标的相对大小是固定的。
基于这个优秀的事实，
判断圆的相互包含关系，这样处理：
画个图就明白了
这个都是基于：“纵坐标相对大小不变”的事实，所以，不管扫描线怎么动，虽然纵坐标变了，但是不用重新建平衡树，因为形态还是不变的
这使得插入的时候，这个树还是正确的，直接找前驱就是对的了
用set就可以
重载小于号，用全局变量P来比较（只有插入和查询前驱的时候会进行比较）
（比较的第二关键字还是有用的，因为同时插入两个半圆壳，纵坐标那个时候是相同的）
由于会出现r=0的情况，所以扫描线的处理，横坐标相同，插入在前，删除在后。
代码：
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(ll &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=+;
int n;
ll P;//PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
struct circle{
ll x,y,r;
int w;
long double calc(ll p,int fl){
return (long double)y+fl*sqrt((long double)r*r-(long double)(p-x)*(p-x));
}
}c[N];
struct po{
int id,fl;//fl=1 up; fl=-1 down
po(){}
po(int x,int y){
id=x;fl=y;
}
bool friend operator <(po a,po b){
if(c[a.id].calc(P,a.fl)!=c[b.id].calc(P,b.fl)) return c[a.id].calc(P,a.fl)<c[b.id].calc(P,b.fl);
return a.fl<b.fl;
}
};
set<po>s;
set<po>::iterator it;
struct que{
int pos,id,typ;
bool friend operator <(que a,que b){
if(a.pos!=b.pos)return a.pos<b.pos;
return a.typ>=b.typ;
}
}q[*N];
int tot;
struct node{
int nxt,to;
}e[*N];
int hd[N],cnt;
int du[N];
int fa[N];
void add(int x,int y){
e[++cnt].nxt=hd[x];
e[cnt].to=y;
hd[x]=cnt;
}
int f[N];
bool vis[N];
void dfs(int x){
vis[x]=;
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(!vis[y]){
dfs(y);
f[x]+=f[y];
}
}
f[x]=max(f[x],c[x].w);
}
int main(){
scanf("%d",&n);
for(reg i=;i<=n;++i){
rd(c[i].x);rd(c[i].y);rd(c[i].r);//rd(c[i].w);
scanf("%d",&c[i].w);
q[++tot].pos=c[i].x-c[i].r;
q[tot].id=i;q[tot].typ=; q[++tot].pos=c[i].x+c[i].r;
q[tot].id=i;q[tot].typ=-;
}
sort(q+,q+tot+);
for(reg i=;i<=tot;++i){
P=q[i].pos;
// cout<<q[i].pos<<" "<<q[i].id<<" "<<q[i].typ<<endl;
// cout<<c[1].calc(P,1)<<" and "<<c[1].calc(P,-1)<<" "<<c[q[i].id].calc(P,1)<<endl;
if(q[i].typ==){
it=s.upper_bound(po(q[i].id,));
if(it!=s.end()){
if((*it).fl==){
// cout<<" find up "<<endl;
fa[q[i].id]=(*it).id;
add((*it).id,q[i].id);
}else{
fa[q[i].id]=fa[(*it).id];
add(fa[(*it).id],q[i].id);
}
}else{
fa[q[i].id]=;
add(,q[i].id);
}
s.insert(po(q[i].id,));
s.insert(po(q[i].id,-));
}else{
s.erase(po(q[i].id,));
s.erase(po(q[i].id,-));
}
}
dfs();
printf("%d\n",f[]);
return ;
} }
signed main(){
freopen("2.in","r",stdin);
freopen("2.out","w",stdout);
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/2/10 8:46:45
*/