题解 P3268 【[JLOI2016]圆的异或并】

· · 题解

扫描线233……

大家还记的如何求圆的并吗？

当然是暴力自适应Simpson积分啦……

但是这道题让你除π输出哦，而且是鬼畜的异或并哦！

所以我们的直觉开始告诉我们这道题可能和寄蒜几盒并不沾多少边

反而像是一些奇怪的东西……

当觉得题目开始辣手的时候，请注意那些奇怪的条件

比如说这道题来讲，我们发现很奇怪的是没有相交的圆，甚至连内切外切都没有

那么我们就要注意了……

也就是说我们发现这些圆的关系可以这样来描述

如果a在b中，b在c中，则a在c中

类比这一句话：

如果a<b,b<c,则a<c

这意味嵌套是有传递性的

再考虑这个性质，如果a在b中，则a被b包含

类比这样一句话

如果 a小于b,则b大于a

这意味着嵌套是有自反性的

要知道，传递性和自反性是小于号的两个基本性质，也是它作为一个返回值为bool运算符的本质……，换句话来讲，假设我们开发出了一个奇怪的运算，使得这个bool返回值的东西也具有传递性和自反性，这个运算符就和小于号逻辑上等价

逻辑上等价意味着我们基于小于号性质开发的所有高速算法和数据结构都可以用了，比如sort，比如set，比如priority_queue

因此我们发现这道题可以用一个优美的扫描线做法搞过去

扫描线

其实扫描线并不是一个玄学的算法，而是一种思想，思想性的东西注定了可以它很难也可以很简单……，真正写程序的时候扫描线并不存在

扫描线通常用来处理二位平面上的一些问题，因为同时处理两维信息会极端辣手，所以我们假象有一条与y轴平行，无限长的直线，从左到右缓慢移动，这样这一条线上的点的x值全部相同，我们就可以专心考虑y的信息了

其实说这个主要是让大家从感情上接纳扫描线，毕竟掌握这玩意还是得靠做题……

首先我们发现把一个整圆插进去是不行的，因为我们需要关注的是这个圆层数的 奇偶性，但是set又是不可重的，所以在同一层的圆会十分辣手……

但是一旦我们换个思路，毕竟现在我们可以使用扫描线这个有力的工具，我们自然会发现，这个图形和扫描线的点交点是高度括号化的，也就是说，我们对于一个圆来讲，发现它上面的最近交点和下面最近交点一定是属于一个圆

因此我们可以考虑不存一个正圆，因为扫描线要计算交点……正圆没法计算

所以拆成两个半圆函数，这个我们就可以维护了

那么我们具体来讲怎么做呢？

首先我们发现按x排序后，每个圆会在x上会有一个出现区间，而且更棒的是如果a嵌套了b 那么a一定比b早出现晚消失

所以我们将一个圆拆成两个操作点，一个加入点，坐标为x-r,一个为删除点，坐标为x+r

之后排序，从小到大处理操作序列

如果这个点是加入点，那么像set里插入一个上圆弧和下圆弧，并且查找上圆弧的前驱（你要查下圆弧后继也行，但是我嫌判end麻烦~）

如果这个前驱是下圆弧，那么这个圆的层数奇偶性应该和前驱的奇偶性相反

如果是上圆弧，那么这个圆的层数奇偶性应该和前驱的奇偶性相同

(还是不懂的话自己画图理解啦~，我懒得插图了……)

此时我们就可以处理每个圆的奇偶性了，暴力的奇加偶减即可

那么如果是删除的话该怎么办呢？set里大力erase即可……

最后一个问题(可能是两个？)

我们该如何定义小于号？

由于是在扫描线，因此我们时刻记录下来扫描线的x坐标，暴力计算每个函数的函数值比较，由于不会相交，所以相对大小关系不变……

另外，插入上圆弧的时候函数值和下圆弧相等，该如何解决？

我们让这两个的值错开一个eps即可……

具体细节看代码吧，不作死还是很好写的

对了，一般这种东西存下标会非常好写，要是存值的话……祝您好运

上代码~

#include<cstdio>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
typedef double db;typedef long long ll;
const int N=2*1e5+10;const db eps=1e-9;
db a[N];db b[N];db r[N];int o[N];int n;db nx;
struct cir//我们这里只存了下标 tp=1/-1 
{
    int tp;int u;cir(int T=0,int N=0){tp=T,u=N;}//这里的计算函数+了一个eps，防止冲突 
    inline db cy(){return b[u]+(db)tp*(sqrt(r[u]*r[u]-(nx-a[u])*(nx-a[u]))+eps);}
    friend bool operator <(cir a,cir b){db jud=a.cy()-b.cy();return jud<-eps;}
};set <cir> s;ll res;
struct pot
{
    int tp;int v;int u;//操作序列点，写了个赋值函数方便压行 
    inline void rv(int T=0,int V=0,int U=0){tp=T;v=V;u=U;}
    friend bool operator <(pot a,pot b){return a.v<b.v;}
}op[2*N];int cnt;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)//读进来 
    {
        scanf("%lf%lf%lf",&a[i],&b[i],&r[i]);
        op[++cnt].rv(1,a[i]-r[i],i);op[++cnt].rv(0,a[i]+r[i],i);
    }sort(op+1,op+cnt+1);//sort一遍 
    for(int i=1;i<=cnt;i++)
    {
        nx=op[i].v;
        if(op[i].tp)
        {
            int nw=op[i].u;set <cir> ::iterator it;
            it=s.insert(cir(1,nw)).first;//set的insert返回一个pair类型 
            if(it==s.begin()){o[nw]=1;}//特判无前驱 
            else //找到前驱 
            {
                --it;if((*it).tp==-1){o[nw]=o[(*it).u]^1;}
                else {o[nw]=o[(*it).u];}
            }
            if(o[nw]){res+=r[nw]*r[nw];}else {res-=r[nw]*r[nw];}//奇加偶减 
            s.insert(cir(-1,nw));//插入下圆弧 
        }else{s.erase(cir(1,op[i].u));s.erase(cir(-1,op[i].u));}//大力erase掉即可 
    }printf("%lld",res);return 0;//拜拜程序~ 
}