2025年扫描线~

科技前沿 • 2025-01-11 20:14 • 阅读 35

大家好，我是讯享网，很高兴认识大家。

突然发现自己好菜~这都不会。。。

来记录一下我学的扫描线
扫描线可以解决矩形面积的问题,如:给出n个矩阵有重叠部分，问你面积（各种面积）。
然后，原理：
乱画的几个矩阵
讯享网
画的歪歪扭扭~~好歪好扭~~
黄线就是扫描线了。
然后线段树里一般维护的是矩形所在当前扫描线上的长度。（说的不太清）
就是就这个
~~好歪好扭凑合吧~~
画括号的长度就是所要维护的长度
横着的长度不用线段树维护因为横着的长度就是a[i]-a[i-1] 。
然后线段树维护的时候有一个特别的地方
就是比如：
正常的线段树区间是1~5 子节点：1~3 4~5
但是这里就会把3~4区间里的东西丢了
所以是1~3 3~5
然后叶子结点的l、r ： l+1==r

//以下只针对这个题
需要在输入的时候标记一下这是矩形的左边界还是右边界（因为维护的时候得判断是加上一条边还是减去一条边）、然后离散化（离散化的时候只用记y坐标就可以因为线段树维护的只有那个东西）、建个空树、然后一个一个边界加。
这个还不用向下传递，因为查询时只用查询最上面的节点就好，删的时候因为是矩形，所以删的时候和加的时候的区间是一个区间（这个问题困了我好久）
给出例题：~~（忘了哪道题。尴尬）~~

poj1542

#include <stdio.h> #include <algorithm> #include <vector> using namespace std; const int maxn = 205; struct Node { 
    int l,r; double num; int cover; }node[maxn<<3]; struct Point { 
    double x,y,yy; int f; bool operator<(const Point& a) const { 
    return x<a.x; } }pot[maxn<<1]; vector<double> vv; int getid(double x) { 
    return lower_bound(vv.begin(),vv.end(),x)-vv.begin()+1; } double getsum(int l,int r) { 
    return vv[r-1]-vv[l-1]; } void build(int l,int r,int no) { 
    node[no].l=l; node[no].r=r; node[no].num=0; node[no].cover=0; if(l+1==r) return; int mid=l+r>>1; build(l,mid,no<<1); build(mid,r,no<<1|1); } void up(int no) { 
    if(node[no].cover) node[no].num=getsum(node[no].l,node[no].r); else node[no].num=node[no<<1].num+node[no<<1|1].num; } void update(int l,int r,int no,int num) { 
    if(node[no].l>=l&&node[no].r<=r) { 
    node[no].cover+=num; up(no); return; } //!!!!!!!!!!!!!这里卡了我一天我太难了  if(l<node[no<<1].r) update(l,r,no<<1,num); if(r>node[no<<1|1].l) update(l,r,no<<1|1,num); up(no); } int main() { 
    int n; int cas=1; while(scanf("%d",&n)&&n) { 
    vv.clear(); int kk=0; for (int i=0;i<n;i++) { 
    double x,xx,y,yy; scanf("%lf%lf%lf%lf",&x,&y,&xx,&yy); pot[kk].x=x; pot[kk].y=y; pot[kk].yy=yy; pot[kk++].f=1; pot[kk].x=xx; pot[kk].y=y; pot[kk].yy=yy; pot[kk++].f=-1; vv.push_back(y); vv.push_back(yy); } sort(pot,pot+kk); sort(vv.begin(),vv.end()); vv.erase(unique(vv.begin(),vv.end()),vv.end()); build(1,vv.size(),1); //printf("%d %d \n",getid(pot[0].y),getid(pot[0].yy)); update(getid(pot[0].y),getid(pot[0].yy),1,pot[0].f); double s=0; for (int i=1;i<kk;i++) { 
    s+=(pot[i].x-pot[i-1].x)*node[1].num; //printf("%d %d %.2lf\n",getid(pot[i].y),getid(pot[i].yy),s); update(getid(pot[i].y),getid(pot[i].yy),1,pot[i].f); } printf("Test case #%d\n",cas++); printf("Total explored area: %.2lf\n\n",s); } return 0; }

讯享网

2025年扫描线~

相关推荐