【BZOJ-4561】圆的异或并 set + 扫描线

4561: [JLoi2016]圆的异或并

Time Limit: 30 Sec  Memory Limit: 256 MB
Submit: 254  Solved: 118
[Submit][Status][Discuss]

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

HINT

Source

Solution

思路还是很显然的，就是看实现的效率了

把一个圆的左右端点分开，来进行扫描，然后用set维护圆与圆的相对位置，

如果扫描完一个圆，就计算这个圆的贡献是+还是-

最后累加答案的时候，将贡献的系数乘进答案即可

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<set>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define MAXN 200010

struct CircleNode{int x,y,r;}c[MAXN];

int T;

struct PointNode

{

    int id,x,f;

    PointNode (int id=,int x=,int f=) : id(id),x(x),f(f) {}

    bool operator < (const PointNode & A) const

        {

            double xx=c[id].y+f*sqrt((long long)c[id].r*c[id].r-(long long)(T-c[id].x)*(T-c[id].x));

            double yy=c[A.id].y+A.f*sqrt((long long)c[A.id].r*c[A.id].r-(long long)(T-c[A.id].x)*(T-c[A.id].x));

            if (xx!=yy) return xx<yy; else return f<A.f;

        }

}P[MAXN<<];

int tp,N,xs[MAXN];

long long ans=;

set<PointNode> st;

set<PointNode> :: iterator ist;

bool cmp(PointNode A,PointNode B) {return A.x<B.x;}

int main()

{

    N=read();

    for (int i=; i<=N; i++)

        c[i].x=read(),c[i].y=read(),c[i].r=read(),

        P[++tp]=PointNode(i,c[i].x-c[i].r,),

        P[++tp]=PointNode(i,c[i].x+c[i].r,-);

    sort(P+,P+tp+,cmp);

//    for (int i=1; i<=tp; i++) printf("%d %d %d\n",P[i].id,P[i].x,P[i].f);

    for (int i=; i<=tp; i++)

        {

            T=P[i].x;

            if (P[i].f==)

                {

                    ist=st.upper_bound(PointNode(P[i].id,,-));

                    if (ist==st.end()) xs[P[i].id]=;

                    else if ((*ist).f==) xs[P[i].id]=-xs[(*ist).id]; else xs[P[i].id]=xs[(*ist).id];

                    st.insert(PointNode(P[i].id,,));

                    st.insert(PointNode(P[i].id,,-));

                }

            else

                st.erase(PointNode(P[i].id,,)),st.erase(PointNode(P[i].id,,-));

        }

    for (int i=; i<=N; i++)

        ans+=(long long)xs[i]*c[i].r*c[i].r;

    printf("%lld\n",ans);

    return ;

}