迎风飘

迎风而立，顺风而飘

扫描线

发布于 2020-11-11 | 分类于 模版 | 13分钟 | 2513字数 | 浏览量：

用于解决矩形相交的相关问题

  • 面积并
  • 周长并

前置知识：

离散化

将点的集体坐标信息覆盖，只保留相对位置及其体现在位置上的性质
当题目中只需要到点之间的相对信息，点的原位置跨度大难以维护时，可以采用离散化

  • 排序二分(unique)
  • 重载运算符
  • 结构体索引(不去重)

排序二分

stl:unique，可以将容器中的相邻元素的重复元素放至容器末端，容器大小并没有改变，返回去重后的尾地址
1.将待离散的容器排序
2.unique去重
3.在去重后的有序序列中二分找到它的位置（lower_bound）
4.将有序序列中它的索引作为它的值

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int a[100010];
int b[100010];
bool cmp(int x,int y){
	return x<y;
}
int main()
{
  int n;
  cin>>n;
  for(int i=1;i<=n;++i){
    cin>>a[i];
    b[i]=a[i];
  }
  sort(b+1,b+1+n,cmp);
  int ant=unique(b+1,b+1+n)-b-1;
  for(int i=1;i<=n;++i){
    a[i]=lower_bound(b+1,b+1+n,a[i])-b;
    cout<<a[i]<<' ';
  }
  cout<<endl;
  return 0;
}

重载运算符

背......(略)

结构体索引

1.结构体储存索引和数值
2.按照数值排序
3.将排序后的索引作为离散后的值

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n;
struct node{
  int x;
  int id;
}a[100010];
bool cmp(node x,node y){
  return x.x<y.x;
}
int main()
{
  int n;
  cin>>n;
  for(int i=1;i<=n;++i){ cin>>a[i].x; a[i].id=i; }
  sort(a+1,a+1+n,cmp);
  for(int i=1;i<=n;++i){
    cout<<a[i].id<<' ';
  }
  return 0;
}

正题：

面积并

思考：
求一个二维平面上若干矩阵叠加之后的面积之和
扫描线从左往右，从右往左，从上到下，从下到上区别都不大，思路都是一致的
我们讨论从下到上的写法
我们考虑将面积并分解成若干的矩阵相加
各个矩阵平行于x轴的边作为分割线是我们十分自然的想法
此时平面中有若干分割线，我们只需要考虑相邻的两条分割线中的面积
读入数据时，我们将所有的分割线存下来

  for(int i=1;i<=n;++i){
    int x_1,x_2,y_1,y_2;
    scanf("%d%d%d%d",&x_1,&y_1,&x_2,&y_2);
    xi[i*2-1]=x_1; xi[i*2]=x_2;
    line[i*2-1]=(scanline){x_1,x_2,y_1,1};
    line[i*2]=(scanline){x_1,x_2,y_2,-1};
  }

我们将x横坐标离散化

bool cmp1(int x,int y){ return x<y; }
bool cmp2(scanline x,scanline y){ return x.h<y.h; }

>>>>>>
  sort(xi+1,xi+1+2*n,cmp1);
  int ant=unique(xi+1,xi+1+2*n)-xi-1;
  for(int i=1;i<=2*n;++i){
    int k1=lower_bound(xi+1,xi+1+ant,line[i].l)-xi;
    int k2=lower_bound(xi+1,xi+1+ant,line[i].r)-xi;
    line[i].l=k1;
    line[i].r=k2;
  }

之后我们按照分割线的y轴坐标将所有的分割线从小到大排序

  sort(line+1,line+1+2*n,cmp2);

如何维护每个两分割线截出来的矩形的面积的高？
相邻分割线的高度相减
如何维护截出来的矩形的长？
线段树！！
在离散后的x值中维护一棵线段树
维护每一个节点中
seg_sum:有多少次被整段地覆盖
seg_len:当前节点被覆盖的长度
我们最后需要的是seg_len[1],即整段序列中有多长被覆盖到
这时候，我们需要push_up()来维护

void push_up(int id,int l,int r){
  if(seg_sum[id]){
    seg_len[id]=xi[r+1]-xi[l];
  }else{
    seg_len[id]=seg_len[id<<1]+seg_len[id<<1|1];
  }
  return;
}

我们判断当前的节点是否被完全地覆盖，如果有，我们直接将离散化前的两点之间的距离来更新它们
如果没有被完全地覆盖，就将左右子节点的有覆盖的长度相加
接下来就是区间的标记操作
我们考虑对于一下分割线，什么时候需要对其进行什么操作
可以发现，我们在首次遇到一个矩阵的一条分割线的时候需要在它覆盖的区间加1
再次遇到一个矩阵中的另一条分割线的时候我们需要将其覆盖的区间-1
我们只需要对其下放到线段树的子节点进行标记操作，即节点+1或者-1
不需要push_down()?
我们需要标记的区间最后会转化为最多log个区间，每个区间我们对其进行标记+1或者减一
可以知道，保证当前被标记的区间+1一定在查询被覆盖长度时被取到
当前覆盖的节点-1操作，我们push_up一下，判断其是否还能被之前的操作所完全覆盖，不行则此节点的答案长度是左右子节点的长度和

void change(int li,int ri,int id,int l,int r,int c){
  if(li<=l&&r<=ri){
    seg_sum[id]+=c;
    push_up(id,l,r);
    return ;
  }
  int mid=(l+r)>>1;
  if(mid>=li){ change(li,ri,id<<1,l,mid,c); }
  if(mid<ri){ change(li,ri,id<<1|1,mid+1,r,c); }
  push_up(id,l,r);
}

模版题**

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define ll long long
#define N 1000010
using namespace std;
int n;
ll ans;
ll xi[N];
struct scanline{
  int l,r,h;
  int mark;
}line[2*N];
ll seg_sum[4*N];
ll seg_len[4*N];
void push_up(int id,int l,int r){
  if(seg_sum[id]){
    seg_len[id]=xi[r+1]-xi[l];
  }else{
    seg_len[id]=seg_len[id<<1]+seg_len[id<<1|1];
  }
  return;
}
void change(int li,int ri,int id,int l,int r,int c){
  if(li<=l&&r<=ri){
    seg_sum[id]+=c;
    push_up(id,l,r);
    return ;
  }
  int mid=(l+r)>>1;
  if(mid>=li){ change(li,ri,id<<1,l,mid,c); }
  if(mid<ri){ change(li,ri,id<<1|1,mid+1,r,c); }
  push_up(id,l,r);
}
bool cmp1(int x,int y){ return x<y; }
bool cmp2(scanline x,scanline y){ return x.h<y.h; }
int main()
{
  scanf("%d",&n);
  for(int i=1;i<=n;++i){
    int x_1,x_2,y_1,y_2;
    scanf("%d%d%d%d",&x_1,&y_1,&x_2,&y_2);
    xi[i*2-1]=x_1; xi[i*2]=x_2;
    line[i*2-1]=(scanline){x_1,x_2,y_1,1};
    line[i*2]=(scanline){x_1,x_2,y_2,-1};
  }
  sort(xi+1,xi+1+2*n,cmp1);
  int ant=unique(xi+1,xi+1+2*n)-xi-1;
  for(int i=1;i<=2*n;++i){
    int k1=lower_bound(xi+1,xi+1+ant,line[i].l)-xi;
    int k2=lower_bound(xi+1,xi+1+ant,line[i].r)-xi;
    line[i].l=k1;
    line[i].r=k2;
  }
  sort(line+1,line+1+2*n,cmp2);
  for(int i=1;i<2*n;++i){
    change(line[i].l,line[i].r-1,1,1,ant-1,line[i].mark);
    ans+=seg_len[1]*(line[i+1].h-line[i].h);
  }
  cout<<ans<<endl;
  return 0;
}

周长并

求若干矩形叠加之后的周长

  • 两次扫描求扫描线长
  • 一次扫描维护端点数

两次扫描
从下到上，从左到右统计扫描线的长度
答案在扫描线的部分长度和中取到
当前扫描线应该加入答案中的长度为：
当前被覆盖的长度与前一次被覆盖的长度之差的绝对值
两次离散化，码量稍大
ps:
将扫描线先后排序时，将高度作为第一关键字，将入边出边作为第二关键字
先扫描入边，再扫描出边
先扫描出边会出现新的入边同时随后覆盖扫描线时，重复计算重叠部分
先扫描入边使得先计算增加的边长，再计算未被覆盖的线段长度，维护了其正确性

周长并模版

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#define ll long long
#define N 100010
using namespace std;
int n;
int xi[N];
int yi[N];
int ans;
struct scan{
  int l,r,h;
  int mark;
}heng[2*N],line[2*N];
int seg_sum[4*N];
int seg_len[4*N];
void push_up(int id,int l,int r,int k){
  if(seg_sum[id]){
    if(k==1)
      seg_len[id]=xi[r+1]-xi[l];
    else
      seg_len[id]=yi[r+1]-yi[l];
  }else{
    seg_len[id]=seg_len[id<<1]+seg_len[id<<1|1];
  }
  return ;
}
void build(int id,int l,int r,int k){
  seg_len[id]=0;
  seg_sum[id]=0;
  if(l==r){
    return ;
  }
  int mid=(l+r)>>1;
  build(id<<1,l,mid,k);
  build(id<<1|1,mid+1,r,k);
  push_up(id,l,r,k);
}
void change(int li,int ri,int id,int l,int r,int c,int k){
  if(li<=l&&r<=ri){
    seg_sum[id]+=c;
    push_up(id,l,r,k);
    return ;
  }
  int mid=(l+r)>>1;
  if(mid>=li){ change(li,ri,id<<1,l,mid,c,k); }
  if(mid<ri){ change(li,ri,id<<1|1,mid+1,r,c,k); }
  push_up(id,l,r,k);
}
bool cmp1(int x,int y){ return x<y; }
bool cmp(scan x,scan y){
  if(x.h==y.h) return x.mark>y.mark;
  return x.h<y.h;
}//注意此处
int main()
{
  scanf("%d",&n);
  for(int i=1;i<=n;++i){
    int x_1,x_2,y_1,y_2;
    scanf("%d%d%d%d",&x_1,&y_1,&x_2,&y_2);
    xi[i*2-1]=x_1; xi[i*2]=x_2;
    yi[i*2-1]=y_1; yi[i*2]=y_2;
    heng[i*2-1]=(scan){x_1,x_2,y_1,1};
    heng[i*2]=(scan){x_1,x_2,y_2,-1};
    line[i*2-1]=(scan){y_1,y_2,x_1,1};
    line[i*2]=(scan){y_1,y_2,x_2,-1};
  }
  n<<=1;
  sort(xi+1,xi+1+n,cmp1);
  sort(yi+1,yi+1+n,cmp1);
  sort(heng+1,heng+1+n,cmp);
  sort(line+1,line+1+n,cmp);
  int antx=unique(xi+1,xi+1+n)-xi-1;
  int anty=unique(yi+1,yi+1+n)-yi-1;
  for(int i=1;i<=n;++i){
    int k1=lower_bound(xi+1,xi+1+antx,heng[i].l)-xi;
    int k2=lower_bound(xi+1,xi+1+antx,heng[i].r)-xi;
    heng[i].l=k1;
    heng[i].r=k2;
    k1=lower_bound(yi+1,yi+1+anty,line[i].l)-yi;
    k2=lower_bound(yi+1,yi+1+anty,line[i].r)-yi;
    line[i].l=k1;
    line[i].r=k2;
  }
  build(1,1,antx,1);
  int shang=0;
  for(int i=1;i<=n;++i){
    change(heng[i].l,heng[i].r-1,1,1,antx,heng[i].mark,1);
    ans+=abs(shang-seg_len[1]);
    shang=seg_len[1];
  }
  shang=0;
  build(1,1,anty,0);
  for(int i=1;i<=n;++i){
    change(line[i].l,line[i].r-1,1,1,anty,line[i].mark,0); 
    ans+=abs(shang-seg_len[1]);
    shang=seg_len[1];
  }
  cout<<ans;
  return 0;
}

维护节点上的端点数

太麻烦....爬

# 模版
树的直径与重心 上一篇
费马小定理 下一篇
Powered by Gridea | © 2019-2020 Theme By HsxyHao
nnez-OIer-Piao
0%
召唤看板娘