因为本题保证两圆之间只有相包含或相离(不用担心两圆重合 因为我没有RE) 所以每个圆之间的相对位置是确定的  也就是可以按极角排序的, 所以可以按横坐标排序后 扫描同时用treap维护加圆删圆(即遇到圆的左边界加圆 遇到又边界删圆   treap中的节点是某个圆的上半部分 或某个圆的下半部分)

具体见其他人的博客   我只想说 我颓废两天、要来的数据全A交上去还是RE  的原因是   windows的rand是32767内的 而BZOJ是Linux也就是说 int x=rand()*rand()=RE;  好的GG、WP&HF   *&%……#&*%……&@#*    恩 转C没转完整的我 的悲剧

贴代码吧 。。

 #include <bits/stdc++.h>
#define LL long long
#define eps 0.000000001
#define N 400005
using namespace std;
struct blu{int l,r,s,w,h;}a[N];
struct bla{int x,d;}c[N];
int rt,n; LL ans,x,z,r[N],u[N],v[N];
bool cm(bla a,bla b){return a.x<b.x||a.x==b.x&&a.d<b.d;}
void up(int o){a[o].s=a[a[o].l].s+a[a[o].r].s+a[o].w;}
void ll(int &o){
int k=a[o].r; a[o].r=a[k].l; a[k].l=o; up(o); up(k); o=k;
}
void rr(int &o){
int k=a[o].l; a[o].l=a[k].r; a[k].r=o; up(o); up(k); o=k;
}
void add(int &o,int t){
if (!o){a[o=t].s=a[o].w; return;}
long double k=sqrt(r[o]*r[o]-(u[o]-x)*(u[o]-x));
k=o>n?v[o]+k:v[o]-k;
if (z<k-eps) add(a[o].l,t); else add(a[o].r,t);
if (a[a[o].l].h>a[o].h) rr(o); else
if (a[a[o].r].h>a[o].h) ll(o); else up(o);
}
void del(int &o,int t){
if (o==t){
if (!a[o].l&&!a[o].r) {o=;return;}
if (a[a[o].l].h>a[a[o].r].h){
rr(o); del(a[o].r,t);
}else{
ll(o); del(a[o].l,t);
}
up(o); return;
}
long double k=sqrt(r[o]*r[o]-(u[o]-x)*(u[o]-x));
k=o>n?v[o]+k:v[o]-k;
if (z<k-eps||abs(z-k)<=eps&&t<=n) del(a[o].l,t); else del(a[o].r,t);
up(o);
}
int qiu(int o){
if (!o) return ;
long double k=sqrt(r[o]*r[o]-(u[o]-x)*(u[o]-x));
k=o>n?v[o]+k:v[o]-k;
if (z<k-eps) return qiu(a[o].l);
return qiu(a[o].r)+a[o].w+a[a[o].l].s;
}
int main(){
srand(); scanf("%d",&n);
for (int i=;i<=n;++i) {
scanf("%lld%lld%lld",&u[i],&v[i],&r[i]);
u[i+n]=u[i]; v[i+n]=v[i]; r[i+n]=r[i];
c[i].d=i; c[i].x=u[i]-r[i];
c[i+n].d=-i; c[i+n].x=u[i]+r[i];
}
sort(c+,c+n+n+,cm);
for (int i=;i<=n;++i) a[i].w=,a[i+n].w=-;
for (int i=;i<=n+n;++i) a[i].h=rand()+; //←就是这 我写了rand()*rand()
for (int i=;i<=n+n;++i)
if (c[i].d>) {
x=c[i].x; z=v[c[i].d];
ans+=r[c[i].d]*r[c[i].d]*(qiu(rt)&?-:);
add(rt,c[i].d); add(rt,c[i].d+n);
}else{
x=c[i].x; z=v[-c[i].d];
del(rt,-c[i].d); del(rt,-c[i].d+n);
}
printf("%lld",ans);
return ;
}

Saber

最新文章

  1. MongoDB入门
  2. python2.x和3.x的区别
  3. swiper初步探索
  4. Leetcode 83 Remove Duplicates from Sorted List 链表
  5. MSSQL 2008错误提示:更改对于登录sa失败
  6. 洛谷P1827 美国血统 American Heritage
  7. Request processing failed; nested exception is org.springframework.dao.InvalidDataAccessApiUsageException: Multiple representations of the same entity解决方法
  8. docker多主机网络方案
  9. 《http权威指南》读书笔记7
  10. Latex常用
  11. [Python] pip 简明指南
  12. 深度学习课程笔记(六)Error
  13. Canvas中 drawImage绘制图片不显示
  14. SQL Server和MySQL数据库
  15. C/C++中#pragma once的使用
  16. 〖Linux〗Kubuntu文件管理器单例的设置(即:一个工作区只一个文件管理器)
  17. django 错误之 ImportError: No module named **
  18. CS小分队第二阶段冲刺站立会议(6月4日)
  19. SO_KEEPALIVE选项
  20. Python Issue: ValueError unknown locale: UTF-8 on OS X (Spyder)

热门文章

  1. 【java基础 3】树形结构数据呈现的递归算法实现
  2. Hankson 的趣味题(codevs 1172)
  3. CodeVs1519 过路费
  4. 【ZJOI2017 Round1练习&amp;BZOJ4766】D1T2 文艺计算姬(Prufer编码)
  5. UINavigationController 小记
  6. python学习之-- importlib模块
  7. BZOJ——4195: [Noi2015]程序自动分析
  8. Android 自己定义UI文章汇总
  9. css中高度比img多出4px的问题
  10. CentOS里route命令详解