POJ_1151 扫描线+离散化+线段树

学线段树的时候学的扫描线（虽然早就看过了，一直没敲过，还是懒），现在来补一道题：

因为题目给的矩形的坐标是浮点型的，所以毫无疑问要离散化，我们以y轴坐标来建立线段树（当然也可以以x轴，这样的话扫描线是上下方向的了），然后Line表示扫描线的下一个位置。求面积的就是ans+=(line[i].x-line[i-1].x)*tree[1].cnt。其实说白了扫描线就是一个区间操作的线段树：不过节点存的是c（这个整个的区间被覆盖的次数，如果为0，则：这个整区间未被完全覆盖）,cnt是整个区间所覆盖的长度。每次只需要更新这两个值就好了，设矩形的左边的权值是1，右边的权值是-1，每一条边覆盖是，总是带着权值覆盖的。

一开始搞成了一个简单的pushup，pushdown操作（可能是两个操作都写挫了）后来发现这样写一直wa，看了kuangbin的博客才知道：这里不需要pushdown，因为矩形的边总是对称的，也就是说并不需要pushdown，等对应边进来的时候直接就把对应加上去的次数给减了（如果强行pushdown，那么下次寻找的时候必须要每次找到叶子节点,复杂度就上去了），不用pushdown的另外一个好处就是pushup比较好写，蠢蠢地wa了三次以后，照着bin神的代码改了才ac了：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll
long long
#define lrt rt<<1
#define rrt rt<<1|1
#define lson
rt<<1,l,mid
#define rson
rt<<1|1,mid+1,r
#define FOR(i,x,y)
for(int i = x;i < y;i ++)
using namespace std;
const int MAXN = 111<<1;
struct Line{
double x,y1,y2;
int f; //记录边是左边还是右边
}line[MAXN];
struct Tree{
int l,r;
int c;
//用来记录该区间被矩形包含的次数
double cnt,lf,rf;
//cnt用来记录矩形实际包含扫描线的长度,lf,rf分别保存这个区间左右的边的浮点值
}tree[MAXN<<2];
bool cmp(Line a,Line b){
return a.x < b.x;
}
double y[MAXN];//用来记录所有点的y坐标
void Build(int rt,int l,int r){
tree[rt].l = l; tree[rt].r = r;
tree[rt].c = 0; tree[rt].cnt = 0;
tree[rt].lf = y[l]; tree[rt].rf = y[r];
if(l+1 == r)
return;
int mid = (l+r)>>1;
Build(lrt,l,mid);
Build(rrt,mid,r);
}
void pushup(int t)
{
if(tree[t].c>0)
{
tree[t].cnt=tree[t].rf-tree[t].lf;
return;
}
if(tree[t].l+1==tree[t].r)
tree[t].cnt=0;
else
tree[t].cnt=tree[t<<1].cnt+tree[t<<1|1].cnt;
}
void Modify(int rt,Line e){
if(tree[rt].lf == e.y1 && tree[rt].rf == e.y2){
tree[rt].c += e.f;
pushup(rt);
return;
}
int mid = (tree[rt].l+tree[rt].r)>>1;
if(e.y2 <= y[mid])
Modify(lrt,e);
else if(e.y1 >= y[mid]) Modify(rrt,e);
else{
Line tem = e;
tem.y2 = y[mid];
Modify(lrt,tem);
tem = e;
tem.y1 = y[mid];
Modify(rrt,tem);
}
pushup(rt);
}
int main()
{
freopen("test.in","r",stdin);
int n,t,tCase = 0;
double x1,y1,x2,y2;
while(scanf("%d",&n),n){
t = 1;
FOR(i,1,n+1){
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
line[t].x = x1;
line[t].y1 = y1;
line[t].y2 = y2;
line[t].f = 1;
y[t] = y1;
t++;
line[t].x = x2;
line[t].y1 = y1;
line[t].y2 = y2;
line[t].f = -1;
y[t] = y2;
t++;
}
sort(line+1,line+t,cmp);
sort(y+1,y+t);
Build(1,1,t-1);
double ans = 0;
Modify(1,line[1]);
FOR(i,2,t){
ans += tree[1].cnt*(line[i].x-line[i-1].x);
Modify(1,line[i]);
}
printf("Test case #%dnTotal explored area: %.2fnn",++tCase,ans);
}
return 0;
}

最后

以上就是纯情故事为你收集整理的POJ_1151 扫描线+离散化+线段树的全部内容，希望文章能够帮你解决POJ_1151 扫描线+离散化+线段树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。