bzoj4561: [JLoi2016]圆的异或并

时间:2022-01-18 23:28:33

Description

在平面直角坐标系中给定N个圆。已知这些圆两两没有交点,即两圆的关系只存在相离和包含。求这些圆的异或面

积并。异或面积并为:当一片区域在奇数个圆内则计算其面积,当一片区域在偶数个圆内则不考虑。

Input

第一行包含一个正整数N,代表圆的个数。接下来N行,每行3个非负整数x,y,r,表示一个圆心在(x,y),半径为r的

圆。保证|x|,|y|,≤10^8,r>0,N<=200000

Output

仅一行一个整数,表示所有圆的异或面积并除以圆周率Pi的结果。

用平衡树维护扫描线与圆的交点

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
typedef long long i64;
const int N=;
int n;
i64 xs[N],ys[N],rs[N],X;
inline i64 p2(i64 x){return x*x;}
inline int _int(){
int x=,c=getchar(),f=;
while(c>||c<){if(c=='-')f=-;c=getchar();}
while(c>&&c<)x=x*+c-,c=getchar();
return x*f;
}
struct pos{
i64 x,y;
int sgn,dep;
i64 r;
double Y(){
i64 a=r-p2(x-X);
if(a<)return y;
return y+sgn*sqrt(a);
}
};
bool operator<(pos a,pos b){
double x=a.Y(),y=b.Y();
if(fabs(x-y)>=.)return x<y;
return a.sgn<b.sgn;
}
struct event{
bool in;
int id;
i64 x(){
if(in)return xs[id]-rs[id];
else return xs[id]+rs[id];
}
}e[N*];
bool operator<(event a,event b){
i64 c=a.x(),d=b.x();
if(c!=d)return c<d;
return a.in<b.in;
}
std::set<pos>line;
int deps[N];
int xp;
i64 xv[N*];
int main(){
n=_int();
for(int i=;i<n;i++){
xs[i]=_int();ys[i]=_int();rs[i]=_int();
xv[i*]=(e[i*]=(event){,i}).x();
xv[i*+]=(e[i*+]=(event){,i}).x();
}
std::sort(e,e+n*);
for(int p=;p<n*;++p){
int id=e[p].id,d;
if(e[p].in){
X=e[p].x();
pos w=(pos){xs[id],ys[id],,,p2(rs[id])};
std::set<pos>::iterator it=line.upper_bound(w);
if(it!=line.end()){
w=*it;
d=(w.sgn==?-w.dep:w.dep);
}else d=;
line.insert((pos){xs[id],ys[id],,d,p2(rs[id])});
line.insert((pos){xs[id],ys[id],-,d,p2(rs[id])});
deps[id]=d;
}else{
X=e[p].x();
line.erase(line.find((pos){xs[id],ys[id],,,p2(rs[id])}));
line.erase(line.find((pos){xs[id],ys[id],-,,p2(rs[id])}));
}
}
i64 ans=;
for(int i=;i<n;i++)ans+=rs[i]*rs[i]*deps[i];
printf("%lld\n",ans);
return ;
}

bzoj4561: [JLoi2016]圆的异或并的更多相关文章

  1. BZOJ4561 JLoi2016 圆的异或并 【扫描线】【set】&ast;

    BZOJ4561 JLoi2016 圆的异或并 Description 在平面直角坐标系中给定N个圆.已知这些圆两两没有交点,即两圆的关系只存在相离和包含.求这些圆的异或面积并.异或面积并为:当一片区 ...

  2. bzoj4561&colon; &lbrack;JLoi2016&rsqb;圆的异或并 圆的扫描线

    地址:http://www.lydsy.com/JudgeOnline/problem.php?id=4561 题目: 4561: [JLoi2016]圆的异或并 Time Limit: 30 Sec ...

  3. BZOJ4561 JLOI2016圆的异或并(扫描线&plus;平衡树)

    考虑一条扫描线从左到右扫过这些圆.观察某一时刻直线与这些圆的交点,可以发现构成一个类似括号序列的东西,括号的包含关系与圆的包含关系是相同的.并且当扫描线逐渐移动时,括号间的相对顺序不变.于是考虑用se ...

  4. &lbrack;BZOJ4561&rsqb;&lbrack;JLOI2016&rsqb;圆的异或并&lpar;扫描线&rpar;

    考虑任何一条垂直于x轴的直线,由于圆不交,所以这条直线上的圆弧构成形似括号序列的样子,且直线移动时圆之间的相对位置不变. 将每个圆拆成两边,左端加右端删.每次加圆时考虑它外面最内层的括号属于谁.用se ...

  5. BZOJ4561&colon; &lbrack;JLoi2016&rsqb;圆的异或并 计算几何&plus;treap

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

  6. 【BZOJ4561】&lbrack;JLoi2016&rsqb;圆的异或并 扫描线

    [BZOJ4561][JLoi2016]圆的异或并 Description 在平面直角坐标系中给定N个圆.已知这些圆两两没有交点,即两圆的关系只存在相离和包含.求这些圆的异或面积并.异或面积并为:当一 ...

  7. 【BZOJ-4561】圆的异或并 set &plus; 扫描线

    4561: [JLoi2016]圆的异或并 Time Limit: 30 Sec  Memory Limit: 256 MBSubmit: 254  Solved: 118[Submit][Statu ...

  8. bzoj 4561&colon; &lbrack;JLoi2016&rsqb;圆的异或并

    Description 在平面直角坐标系中给定N个圆.已知这些圆两两没有交点,即两圆的关系只存在相离和包含.求这些圆的异或面 积并.异或面积并为:当一片区域在奇数个圆内则计算其面积,当一片区域在偶数个 ...

  9. BZOJ 4561 &lbrack;JLoi2016&rsqb;圆的异或并 ——扫描线

    扫描线的应用. 扫描线就是用数据结构维护一个相对的顺序不变,带修改的东西. 通常只用于一次询问的情况. 抽象的看做一条垂直于x轴直线从左向右扫过去. 这道题目要求求出所有圆的异或并. 所以我们可以求出 ...

随机推荐

  1. SQLite 加密 -- SQLCipher

    SQLite3 插件 github 下载地址 插件配置步骤地址 购买地址 其他加密方式介绍 SQLCipher API 地址 前言 应用使用 SQLite 来存储数据,很多时候需要对一部分的数据进行加 ...

  2. 新版react踩坑总结

    使用es6语法与原本es5语法几个有区别的地方 1.React.creatClass与React.Component var Component = React.createClass({ rende ...

  3. Swift-ImageView响应点击事件

    随着Swift语言的不断更新迭代,纯Swift语言编写的代码更加紧凑简单,结合StoryBorad的使用,使开发苹果APP的门槛降低了不少.个人也是比较推荐使用Interface Builder去生成 ...

  4. &lbrack;转载&rsqb;ExtJs4 笔记(12) Ext&period;toolbar&period;Toolbar 工具栏、Ext&period;toolbar&period;Paging 分页栏、Ext&period;ux&period;statusbar&period;StatusBar 状态栏

    作者:李盼(Lipan)出处:[Lipan] (http://www.cnblogs.com/lipan/)版权声明:本文的版权归作者与博客园共有.转载时须注明本文的详细链接,否则作者将保留追究其法律 ...

  5. HTML回顾

    <frameset>和<body>是同一级的,已经在html5中被弃用    结合---->    效果   注意::::span标签不自动换行****

  6. 使用Python给要素添加序号

    在ArcGIS的属性表中,由于编辑修改的原因,默认的FID或OID并不连续,经常需要给要素添加连读的序号,可使用Python代码完成. rec=-1 def autoIncrement(): glob ...

  7. C&num;中override和overload的区别

    重载应该叫overload,重写叫override:重载某个方法是在同一个类中发生的!重写是在子类中重写父类中的方法. 1.override:   父类:public virtual string T ...

  8. java抽象类和接口详解

    接口和内部类为我们提供了一种将接口与实现分离的更加结构化的方法. 抽象类与接口是java语言中对抽象概念进行定义的两种机制,正是由于他们的存在才赋予java强大的面向对象的能力.他们两者之间对抽象概念 ...

  9. Jquery选择器 讲解

    在Dom 编程中我们只能使用有限的函数根据id 或者TagName 获取Dom 对象. 然而在jQuery 中则完全不同,jQuery 提供了异常强大的选择器用来帮助我们获取页面上的对象, 并且将对象 ...

  10. Photoshop:路径填充边缘虚化问题

    怎么才能不让它虚化呢?  解决方案一: 1.同样画出路径 2.新建图层 3.回到路径面板,右击路径图层,选择“填充路径” 4.把“羽化”设置为0,取消选择“消除锯齿” 换个背景色看看效果:一点虚化都没 ...