本文主要是介绍Atlantis HDU - 1542 （扫描线 + 线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://cn.vjudge.net/problem/HDU-1542
题意
求矩形覆盖的面积
思路
模板题
#include <bits/stdc++.h>using namespace std;
const int maxn = 210;
int n,cnt,num,p;
double ls[maxn*2],ans;
struct edg ///边
{double l,r,h;int flag; ///1为下线 -1为上线bool operator < (const edg &b)const{return h < b.h;}
}edge[maxn];
struct node ///线段树
{int l,r,lazy;double len;
}tree[maxn*4];void add(double x1,double x2,double h,int f)
{edge[cnt].l = x1;edge[cnt].r = x2;edge[cnt].h = h;edge[cnt++].flag = f;
}void build(int rt,int l,int r)
{tree[rt].l = l;tree[rt].r = r;tree[rt].len = 0;tree[rt].lazy = 0;if(l == r) return ;int mid = (l+r)>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
}
void pushup(int rt)
{if(tree[rt].lazy) /// 存在{tree[rt].len = ls[tree[rt].r+1] - ls[tree[rt].l];}else if(tree[rt].l == tree[rt].r) ///最小距离 为0{tree[rt].len = 0;}else tree[rt].len = tree[rt<<1].len + tree[rt<<1|1].len; ///不存在整段 但可能存在部分
}
void updata(int rt,int l,int r,int val)
{if(tree[rt].l == l&&tree[rt].r == r){tree[rt].lazy += val;///新增或者去掉pushup(rt);return ;}int mid = (tree[rt].l + tree[rt].r)>>1;if(l > mid)updata(rt<<1|1,l,r,val);else if(mid >= r)updata(rt<<1,l,r,val);else{updata(rt<<1,l,mid,val);updata(rt<<1|1,mid+1,r,val);}pushup(rt);}
int main()
{int i,j,k;int ca = 1;while(scanf("%d",&n) != EOF&&n){ans = cnt = p = 0;for(i=1;i<=n;i++){double x1,x2,y1,y2;scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);add(x1,x2,y1,1);add(x1,x2,y2,-1);ls[p++] = x1;ls[p++] = x2;}sort(edge,edge+cnt); ///从下向上扫描sort(ls,ls+p);int m = unique(ls,ls+p) - ls; ///去重 m为驱虫后元素个数build(1,0,m-1);for(i=0;i<cnt-1;i++){int l = lower_bound(ls,ls+m,edge[i].l) - ls; ///找到对应的位置int r = lower_bound(ls,ls+m,edge[i].r) - ls;updata(1,l,r-1,edge[i].flag); ///修改ans += (edge[i+1].h - edge[i].h) * tree[1].len;///只有有高度差才会改变}printf("Test case #%d\n",ca++);printf("Total explored area: %.2f\n\n",ans);}return 0;
}
这篇关于Atlantis HDU - 1542 （扫描线 + 线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
