一个经典的扫描线问题

题目

4561: [JLoi2016]圆的异或并

Time Limit: 30 Sec Memory Limit: 256 MB

Description

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

第一行包含一个正整数\(N\),代表圆的个数。接下来\(N\)行,每行\(3\)个非负整数\(x,y,r\),表示一个圆心在\((x,y)\),半径为\(r\)的圆。保证\(|x|,|y|≤10^8,r>0,N<=200000\)

Output

仅一行一个整数,表示所有圆的异或面积并除以圆周率\(π\)的结果。 # 解题报告 考场上打了暴力滚粗了。 如果知道每个圆包含他的半径最小的圆,那建出树,用圆的面积乘上\((-1)^h\)求和就是答案,这就是暴力的打法; 正解是维护一条竖直(或水平)扫描线上每个圆的交点坐标,将每个圆最靠左,最靠右的两点的横坐标上放置左右括号$ ( )\(,标记该圆加入、退出扫描线。每个\)i$圆加入扫描线的时候,查询 $ y_i $ 上方的第一个点 \(y_j\) .很显然,如果 \(y_j\) 是一个圆 \(j\) 在扫描线上偏下的点,那么\(i\)\(j\)并列在同一层,系数相同;如果 $ y_j $ 是\(j\)在扫描线上偏上的点,那么\(i\)\(j\)内,系数\(k*(-1)\); 查询后继,set就可以

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
const int N=200001;
char *cp=(char *)malloc(6000000);
struct circle {
int x,y,r;
circle(int x=0,int y=0,int r=0)
:x(x),y(y),r(r){}
} c[N];
struct point {
int p,x,k;
point(int p=0,int x=0,int k=0)
:p(p),x(x),k(k){}
} p[N<<1];
struct height {
int p,k;
height(int p=0,int k=0)
:p(p),k(k){}
};
int n,tot,tmp,k[N];
set<height> s;
long long ans;
inline void in (int &x) {
int f=1;
for (;*cp<'0'||*cp>'9';cp++)
if (*cp=='-') f=-1;
for (x=0;*cp>='0'&&*cp<='9';cp++)
x=x*10+*cp-48;
x*=f;
}
inline bool cmp(point a,point b){
return a.x<b.x;
}
inline long long cal(long long x){
return x*x;
}
inline long long mul(long long x,long long y){
return x*y;
}
bool operator < (const height a,const height b){
double x=(double)c[a.p].y+(double)a.k*sqrt(cal(c[a.p].r)-cal(tmp-c[a.p].x));
double y=(double)c[b.p].y+(double)b.k*sqrt(cal(c[b.p].r)-cal(tmp-c[b.p].x));
return x!=y?x<y:a.k<b.k;
}
int main() {
// freopen("circle.in","r",stdin);
// freopen("circle.out","w",stdout);
fread(cp,1,6000000,stdin);
in(n); int x,y,z;
for (int i=1;i<=n;i++) {
in(x),in(y),in(z);
c[i]=circle(x,y,z);
p[++tot]=point(i,x-z,1);
p[++tot]=point(i,x+z,-1);
}
sort(p+1,p+1+tot,cmp);
for (int i=1;i<=tot;i++) {
tmp=p[i].x;
if (p[i].k==1) {
set<height>:: iterator it;
it=s.upper_bound(height(p[i].p,1));
if (it==s.end())
k[p[i].p]=1;
else
if (it->k==1)
k[p[i].p]=k[it->p]*(-1);
else
k[p[i].p]=k[it->p];
s.insert(height(p[i].p,1));
s.insert(height(p[i].p,-1));
}else {
s.erase(height(p[i].p,1));
s.erase(height(p[i].p,-1));
}
}
for (int i=1;i<=n;i++)
ans=ans+mul(k[i],cal(c[i].r));
printf("%lld\n",ans);
return 0;
}

留言