泰安做网站建设的公司,wordpress 双栏目,淄博公司制作网站有哪些,企业微信网站开发公司解析
很神奇的一道题。
关键条件#xff1a;任意两个圆无交。 把一个圆分成上下两个圆弧#xff0c;那么所有圆弧的高度关系不会发生变化。 所以可以开一个 set#xff0c;维护一个从左往右扫的扫描线#xff0c;按照当前扫描线的横坐标定义比较符号#xff0c;在圆的最…解析
很神奇的一道题。
关键条件任意两个圆无交。 把一个圆分成上下两个圆弧那么所有圆弧的高度关系不会发生变化。 所以可以开一个 set维护一个从左往右扫的扫描线按照当前扫描线的横坐标定义比较符号在圆的最左处把圆弧放进去再在最右边把圆弧删掉。每次插入时找到前驱即可确定其被包含的圆的层数。 注意精度
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
using namespace std;const int N4e5100;
const int M50050;
const int mod1e97;
const double eps1e-9;inline ll read() {ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}int n,m;double x[N],y[N],r[N];
double now;
int num[N];struct cir {int id,op;cir(int a0,int b0) {ida;opb;}double h(){return y[id]op*(sqrt(r[id]*r[id]-(x[id]-now)*(x[id]-now))eps);}
};
bool operator (cir a,cir b) {return a.h()b.h();
}
setcirs;
struct ope {int x,id,op;bool operator (const ope oth) {return xoth.x;}
} o[N];
int tot;int main() {
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifnread();for(int i1; in; i) {scanf(%lf%lf%lf,x[i],y[i],r[i]);o[tot](ope) {(int)(x[i]-r[i]),i,1};o[tot](ope) {(int)(x[i]r[i]),i,-1};}sort(o1,o1tot);for(int i1; itot; i) {nowo[i].x;if(o[i].op1) {//printf(ins: %d\n,o[i].id);setcir::iterator its.insert((cir) {o[i].id,1}).first; if(it!s.begin()) {it--;cir c*it;//printf( pre%d\n,c.id);num[o[i].id]num[c.id]^(c.op-1);}s.insert((cir){o[i].id,-1});}else {s.erase((cir) {o[i].id,1});s.erase((cir) {o[i].id,-1});}}ll ans0;for(int i1; in; i) {if(num[i]0) ansr[i]*r[i];else ans-r[i]*r[i];//printf(i%d num%d\n,i,num[i]);}printf(%lld\n,ans);return 0;
}
/*5 37 1 4 1 91 3 5 31 1 4 22 3 5
*/
