题解：P3268 [JLOI2016] 圆的异或并

liaiyang · 2024-03-26 10:16:34 · 题解

update 2024.3.26 为了叉掉人类智慧贡献了组 hack。

update 2024.8.20 修改了精度问题，可以过掉新的 hack。

我们将圆切成上半圆和下半圆，用 set 维护，按照 y 值比较。

为了防止上下半圆被认为相等，给上圆加上一个 eps。

把圆的最左最右加入，从左向右扫描线，扫到时寻找当前下半圆的前驱，如果是上半圆就相离，否则包含。

建出一颗圆的森林，按照 dep 求当前圆的面积贡献即可。

时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lc now<<1
#define rc now<<1|1
#define y1 Y1
#define min(a,b) (a<b?a:b) 
#define max(a,b) (a>b?a:b)
#define P pair<int,int>
#define x first
#define y second
#define modd(x) (((x)%mod+mod)%mod) 
#define rd read()
#define lowbit(x) ((x)&(-x))
#define abs(x) ((x)<0?-(x):(x))
mt19937 rnd(time(0));
inline int read(int u=0, char c=getchar(), bool f=false){
    for (;!isdigit(c);c=getchar()) f|=c=='-';
    for (;isdigit(c);c=getchar()) u=(u<<1)+(u<<3)+c-'0';
    return f?-u:u;
}
inline void wt(int x){
    if(x<0) x=-x,putchar('-');
    if(x>9) wt(x/10);
    putchar(x%10+48);
}
inline void wt(int x,char k){wt(x),putchar(k);}
const int inf=~0U>>1,linf=~0ULL>>1; 
const int mod=998244353;
const int N=2e5+10;
const double eps=1e-3;
int now,ans;
struct node{
    int x,y,r,pos;
    int id;
    bool flag;
    double check()const{return flag?y+sqrt(r*r-(x-now)*(x-now))+eps:y-sqrt(r*r-(x-now)*(x-now));}
    bool operator<(const node v)const{return check()<v.check();}
}a[N<<1];
set<node>s;
int n,f[N],dep[N];
main(){
    n=rd;
    for(int i=1;i<=n;i++){
        int x=rd,y=rd,r=rd;
        a[i]={x,y,r,x-r,i,1};
        a[i+n]={x,y,r,x+r,i,0};
    }
    sort(a+1,a+2*n+1,[](node x,node y){return x.pos<y.pos;});
    for(int i=1;i<=2*n;i++){
        now=a[i].pos;
        if(a[i].flag){
            s.insert({a[i].x,a[i].y,a[i].r,a[i].pos,a[i].id,0});
            s.insert({a[i].x,a[i].y,a[i].r,a[i].pos,a[i].id,1});
            auto it=s.lower_bound({a[i].x,a[i].y,a[i].r,a[i].pos,a[i].id,0});
            if(it==s.begin()) dep[it->id]=1;
            else{
                it--;
                if(it->flag) dep[a[i].id]=dep[it->id];
                else dep[a[i].id]=dep[it->id]+1;
            }
            ans+=((dep[a[i].id]&1)?1:-1)*a[i].r*a[i].r;
        }
        else{
            s.erase({a[i].x,a[i].y,a[i].r,a[i].pos-2*a[i].r,a[i].id,0});
            s.erase({a[i].x,a[i].y,a[i].r,a[i].pos-2*a[i].r,a[i].id,1});
        }
    }
    wt(ans,'\n');
    return 0;
}