线段树扫描线hdu1828Picture

线段树扫描线hdu1828Picture ： http://acm.hdu.edu.cn/showproblem.php?pid=1828

思路：求矩形周长并……可以把矩形分成横线和竖线两部分，并将两条横线和两条竖线都分别标记为-1、1。然后建两遍数，将结果相加就可以了（也有其他建一遍树的做法）……但这个题值得说的就是用这种做法有一个坑……将矩形的横线和竖线的坐标按照从小到大（从大到小）的顺序排序，当两个矩形有边重合时得先把值为1（或-1）的边先加进去。如A矩形是【（0,0），（1,1）】，矩形B是【（1,0），（2,1）】，这样矩形A的右侧边和矩形B的左侧边重合了，假如我们规定左侧边标记为1，右侧边标记为-1，并且按从小到大排序，那么我们应该先把矩形B的左侧边先于A的右侧边加进去……这是因为如果先加A的右侧边，那么我们在pushup的时候先把标记加上了，此时对应的该标记为0了（1和-1抵消），这样sum就会被更新为0，这样会导致当前的sum和上一个sum间造成一个差值，从而导致A的右边和B的左边都重复计算……

在这里，我已经wa到死了……看了别人的写法发现和自己的就只有这里不同感觉很涨姿势，仔细想想才发现存在这样的差别……

#include<map>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long LL;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const int maxn=1e5+10;
const int MAXM = 1e5+10;
int cnt;
struct Line {
int val,u,v;
int id;
bool operator < (const Line &a)const {
return val < a.val;
}
} lx[maxn*2],ly[maxn*2];
int ans = 0;
int sum[MAXM*2],vis[MAXM*2];
void up(int l,int r,int rt) {
if(vis[rt]) sum[rt] = r-l+1;
else if(l == r) sum[rt] = 0;
else sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void update(int L,int R,int id,int l,int r,int rt) {
if(L <= l && r <= R) {
vis[rt] += id;
up(l,r,rt);
return;
}
int m = l+r>>1;
if(L <= m)update(L,R,id,lson);
if(R > m)update(L,R,id,rson);
up(l,r,rt);
}
void solve(int L,int R,struct Line *t) {
memset(vis,0,sizeof(vis));
memset(sum,0,sizeof(sum));
int pre = 0;
for(int i = 0; i < cnt; i++) {
int l = t[i].u,r = t[i].v;
update(l,r-1,t[i].id,L,R,1);
ans += abs(pre-sum[1]);
pre = sum[1];
}
}
int main() {
//
freopen("in.txt","r",stdin);
int n,x1,x2,y1,y2;
while(scanf("%d",&n) != EOF) {
if(n == 0) {
printf("0n");
continue;
}
cnt = 0;
ans = 0;
for(int i = 0; i < n; i++) {
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x1 += 10001,x2 += 10001,y1 += 10001,y2 += 10001;
lx[i].val = y1,lx[i].u = x1,lx[i].v = x2,lx[i].id = 1;
lx[i+n].val = y2,lx[i+n].u = x1,lx[i+n].v = x2,lx[i+n].id = -1;
// 以前是这样写的：
// lx[cnt].val = y1,lx[cnt].u = x1,lx[cnt].v = x2,lx[cnt].id = 1;
// lx[cnt+1].val = y2,lx[cnt+1].u = x1,lx[cnt+1].v = x2,lx[cnt+1].id = -1;
// 这样就使得A的右侧边先于B的左侧边加进去了，影响了排序的结果
ly[i].val = x1,ly[i].u = y1,ly[i].v = y2,ly[i].id = 1;
ly[i+n].val = x2,ly[i+n].u = y1,ly[i+n].v = y2,ly[i+n].id = -1;
}
cnt = 2*n;
sort(lx,lx+cnt);
sort(ly,ly+cnt);
memset(vis,0,sizeof(vis));
memset(sum,0,sizeof(sum));
solve(0,20001,lx);
solve(0,20001,ly);
printf("%dn",ans);
}
return 0;
}

最后

以上就是受伤香水为你收集整理的线段树扫描线hdu1828Picture的全部内容，希望文章能够帮你解决线段树扫描线hdu1828Picture所遇到的程序开发问题。

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