【面积并】扫描线

挺抽象的一个算法…… 这里说的是面积并的用法，~周长并还没学~

题目【扫描线】

算法思路

如果图是一张 我偷的一张图片

这是一张图片，然后我们定义扫描面积的线为各个矩形与x轴平行的边，如红线

但是并不是所有的线对答案都有贡献，只有进入矩形的那一条的线对答案有贡献，出矩阵的那一条线没有贡献。

那就将线段定义为入线 （红） 和 出线（蓝）。

到此，我们就可以从整个矩形的最下方开始对矩形进行扫描。

1. 当扫描到第一条线的时候，发现是入线，然后对这条线的横坐标区间打上贡献。

2. 当扫描到第二条线的时候，同样也是入线，对横坐标打上标记，然后之前的横坐标移动了两条线之间间隔的宽度，该部分的面积为具有贡献的横坐标的总长度 * 两条线高度的差值

3. 同理扫描到第三条线的时候，先计算具有贡献的横坐标移动了多少的高度，然后这条边是出线。就把出去的贡献给删除。

4. 最后移动到最后一条线段上，让最后一条线段计算扫描后的面积。

5. 将每一步得到的答案求和，就可以得到总面积

   读入操作

6. 读入矩形，坐标为x ~ x2覆盖的贡献值，y为下面的那一条边，所以 x ~ x2 高度为y的线为入线，另一条为出线

7. 存下x点，后续只需要记录覆盖的点是从哪个位置到哪个位置就可以了

cin>>x>>y>>x2>>y2;
    //读入矩形
    X[2*i-1]=x,X[i*2]=x2;
    //将每一个x点放入X集合内，用于建树
    line[i*2-1]=( Scanline ) { x,x2,y,1 };
    //建立扫描线，这根扫描线是从x到x2开始，高度为y的入边
    line[ i*2 ]=( Scanline ) { x,x2,y2,-1};

离散化x坐标和扫描线

1. 将扫描线按y轴排序，将x排序，并去重，得到x点的有序去重集（统计答案的时候，就只需要记录是排名第几的点和第几的点之间有贡献，有贡献的就记录坐标和就可以了）。

sort(line+1,line+1+n);//给扫描线排序，用纵坐标排序，从下往上扫描
  sort( X+1,X+n+1 );    //给点排序，建树
  int tot=unique( X+1,X+n+1 )-X-1;//去重点

建树

与普通线段树不同的是，这里的每一个节点都向右偏移了一个单位 因为：

1. 在矩形中，肯定不是左右两个点重合的对吧
2. 看一下下面的例子： [1,8]的线段树，他的两个儿子是[1,4] , [5,8]。 如果我们要扫描到 [1,5]的线的话，更新的时候就会更新到 [1,4], [5,5]这个区间。 得到的长度就是 [1,4] + [5,5]的长度，那么这样就会出错，因为[5,5]的长度为0，得到了覆盖的坐标为 (4-1)+(5-5)的总长度。 解决办法： 将叶子节点延伸一个节点的长度，实现 [4]节点存的是 [4,5] 节点信息，这样我们要记录[1,5] 节点信息的时候，就只需要记录 [1,4]就可以了，同理，我们需要记录 [1,4]的时候就只需要给 [1,2] [3,3]打上标记就可以了。以此类推。(真的好难想啊）。

build(1,1,tot-1);  //建树，因为可能会出现区间并不连续的情况，所以在这里叶子节点其实是向右扩展了一个单位的

void build(int x,int l,int r)
{
  tree[x].l=l,tree[x].r=r;
  tree[x].len=0;
  tree[x].sum=0;
  if( l==r ) return;
  int mid=(l+r>>1);
  build(lson,l,mid);
  build(rson,mid+1,r);
}

区间更新

其实这里也就是普通的线段树操作，但还要记录下来的原因是因为这里还是用了巧妙的方法。

1. 更新的时候两个方向都直接去更新，由于建树的时候节点右移了一个单位所以这里区间更新会有所不同。

void pushup(int x)
{
  int l=tree[x].l,r=tree[x].r;
  if( tree[x].sum )  //如果被入边扫描过，那他的值就更新为第r个点到第l个点的长度
      tree[x].len=X[r+1]-X[l];
  else
    tree[x].len=tree[lson].len+tree[rson].len;
   //反之没有被扫描就是他儿子的长度和
}

void update(int x,ll L,ll R,int c)//L,R为需要扫描的范围，c为扫描线的性质
{
  int l=tree[x].l,r=tree[x].r;
  if( X[r+1]<=L or R<=X[l] ) return;
  //扫错了，这个区间完全在所需要的范围之外
  if( L<=X[l] and X[r+1]<=R )  //节点右移了一个单位
  {
    tree[x].sum+=c;
    pushup(x);
    return;
  }
  //如果该扫描线完全包含了该区间，那么就更新该区间的扫描性质和长度
  update(lson,L,R,c);
  update(rson,L,R,c);
  //反之，两边都扫一下，扫错了会返回的
  pushup(x);
}

扫描

1. 利用线段树去将这条扫描线覆盖的坐标打上标记
2. 然后总的有几条线的坐标打上了标记，用打上标记的总数*覆盖的高度就可以计算出这次扫描经过的面积

for(int i=1;i<n;i++){
    update( 1,line[i].l,line[i].r,line[i].mark ); //让扫描线去扫一下
    ans+=tree[1].len*( line[i+1].h-line[i].h );
   //更新扫描线的值  
}

至此扫描线的基本原理就这些了，话不多说，看整体代码

Code

#include<bits/stdc++.h>
#define lson (x << 1)  //左儿子
#define rson (x << 1 | 1)  //右儿子
using namespace std;
const int N=1e6+12;
typedef long long ll;
int n,cnt=0;
ll x,y,x2,y2,X[N<<1];
//  x和y为读入的坐标

struct Scanline{
  ll l,r,h;  
 //l为扫描线的左端，r为右端，h为该线在y轴上的高度
  int mark;
 //该扫描线的性质正为入边，负为出边
  bool operator <(const Scanline &other) {return h<other.h;}
//按扫描线的纵坐标排序
}line[N<<1];
//扫描线

struct Setree{
  int l,r,sum;
  //这个节点所维护的区间范围
  //sum值表示这个区间是否被入边扫描过
  ll len;
 //这个区间的长度
}tree[N<<2];
//线段树，维护x坐标离散后扫描到的长度

void build(int x,int l,int r)
{
  tree[x].l=l,tree[x].r=r;
  tree[x].len=0;
  tree[x].sum=0;
  if( l==r ) return;
  int mid=(l+r>>1);
  build(lson,l,mid);
  build(rson,mid+1,r);
}
//建树没什么好说的

void pushup(int x)
{
  int l=tree[x].l,r=tree[x].r;
  if( tree[x].sum )  //如果被入边扫描过，那他的值就更新为第r个点到第l个点的长度
      tree[x].len=X[r+1]-X[l];
  else
    tree[x].len=tree[lson].len+tree[rson].len;
   //反之没有被扫描就是他儿子的长度和
}
//向上传递更新后的值

void update(int x,ll L,ll R,int c)//L,R为需要扫描的范围，c为扫描线的性质
{
  int l=tree[x].l,r=tree[x].r;
  if( X[r+1]<=L or R<=X[l] ) return;
  //扫错了，这个区间完全在所需要的范围之外
  if( L<=X[l] and X[r+1]<=R )
  {
    tree[x].sum+=c;
    pushup(x);
    return;
  }
  //如果该扫描线完全包含了该区间，那么就更新该区间的扫描性质和长度
  update(lson,L,R,c);
  update(rson,L,R,c);
  //反之，两边都扫一下，扫错了会返回的
  pushup(x);
}
//扫描线扫描过程

int main(){
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>x>>y>>x2>>y2;
    //读入矩形
    X[2*i-1]=x,X[i*2]=x2;
    //将每一个x点放入X集合内，用于建树
    line[i*2-1]=( Scanline ) { x,x2,y,1 };
    //建立扫描线，这根扫描线是从x到x2开始，高度为y的入边
    line[ i*2 ]=( Scanline ) { x,x2,y2,-1};
    //反之这是根出边  
}
  n<<=1;
  sort(line+1,line+1+n);//给扫描线排序，用纵坐标排序，从下往上扫描
  sort( X+1,X+n+1 );    //给点排序，建树
  int tot=unique( X+1,X+n+1 )-X-1;//去重点
  build(1,1,tot-1);  //建树，因为可能会出现区间并不连续的情况，所以在这里叶子节点其实是向右扩展了一个单位的
  ll ans=0;
  for(int i=1;i<n;i++){
    update( 1,line[i].l,line[i].r,line[i].mark ); //让扫描线去扫一下
    ans+=tree[1].len*( line[i+1].h-line[i].h );
   //更新扫描线的值  
}
  cout<<ans;
}