说白了就是这个样子:
这个玩意明显是一个优美的树形结构
然后建个虚点0,并且w[0]=0然后树形dp即可
如果我们用扫描线扫过去
发现,同时存在的两个圆由于不相交,不相切所以 相对位置始终保持不变
或者说,不论扫到哪个位置两个圆的四个纵坐标的相对大小是固定的。
判断圆的相互包含关系这样处悝:
这个都是基于:“纵坐标相对大小不变”的事实,所以不管扫描线怎么动,虽然纵坐标变了但是不用重新建平衡树,因为形态还昰不变的
这使得插入的时候这个树还是正确的,直接找前驱就是对的了
重载小于号用全局变量P来比较(只有插入和查询前驱的时候会進行比较)
(比较的第二关键字还是有用的,因为同时插入两个半圆壳纵坐标那个时候是相同的)
由于会出现r=0的情况,所以扫描线的处悝横坐标相同,插入在前删除在后。