OI

BZOJ 4561: [JLoi2016]圆的异或并

Description

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

Input

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

Output

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

Sample Input

2

0 0 1

0 0 2

Sample Output

3

Solution

来一条扫描线，从左向右扫描，遇到一个圆的左边就把这个圆的上半部分和下半部分压入一个set，然后看它下半部分的严格后继是什么，如果是一个下半圆，那么这个下半圆和这个圆贡献不同，否则贡献相同。

如何比较两个圆？

  1. 来自同一个圆时，下>上

  2. 相离时，纵坐标大的越小

  3. 包含时，上下半圆顶点越大的越小

（其实是相反的问题，YY一下。。。）

 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

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
typedef long long LL;
const int INF=1000000007;
const int N=200005;
struct Cir{LL x,y,r;}c[N];
struct node{int id;};
inline int getint() {
    int r = 0; bool b = true; char c = getchar();
    while ('0' > c || c > '9') {if (c == '-') b = false; c = getchar();}
    while ('0' <= c && c <= '9') {r = r * 10 + (c - '0'); c = getchar();}
    if (b) return r;
    return -r;
}
inline bool operator < (node o1,node o2) {
    if (abs(o1.id)==abs(o2.id)) return o1.id>o2.id;
    Cir c1=c[abs(o1.id)],c2=c[abs(o2.id)];
    if ((c1.x-c2.x)*(c1.x-c2.x)+(c1.y-c2.y)*(c1.y-c2.y)>(c1.r+c2.r)*(c1.r+c2.r)) return c1.y>c2.y;
    LL p1=c1.y+c1.r*o1.id/abs(o1.id);
    LL p2=c2.y+c2.r*o2.id/abs(o2.id);
    return p1>p2;
}
inline bool cmp(int o1,int o2) {
    LL p1=c[abs(o1)].x-c[abs(o1)].r*(LL)(abs(o1)/o1);
    LL p2=c[abs(o2)].x-c[abs(o2)].r*(LL)(abs(o2)/o2);
    return (p1<p2)||((p1==p2)&&(o1<o2));
}
set <node> s;
set <node>::iterator it;
int n,b[N*2];
LL ans,gx[N];
int main()
{n=getint();
    for (int i=1; i<=n; i++) 
    {c[i].x=getint();c[i].y=getint();c[i].r=getint();
        b[i]=i;b[i+n]=-i;
    }
    sort(b+1,b+1+2*n,cmp);
    c[n+1].x=c[n+1].y=0;c[n+1].r=INF;gx[n+1]=-1;
    s.insert((node) {n+1});
    s.insert((node) {-(n+1)});
    for (int i=1; i<=2*n; i++) {
        if (b[i]>0) {
            it=s.upper_bound((node){-b[i]});
            if ((*it).id<0) gx[b[i]]=-gx[-(*it).id];
            else gx[b[i]]=gx[(*it).id];
            s.insert((node){b[i]});
            s.insert((node){-b[i]});
        } else {
            s.erase((node){b[i]});
            s.erase((node){-b[i]});
        }
    }
    for (int i = 1; i <= n; ++i) ans += gx[i] * c[i].r * c[i].r;
    printf("%lld",ans);
}