POJ 1177 线段树+扫描线

题意

给一堆正方形，问组合图形周长

题解

首先可以做扫描线入门题HDU 1542。了解了扫描线的原理之后，这道题其实就非常简单了。尤其是POJ还没有判重边。
可以直接用最粗暴的方式，横向扫描一次，纵向扫描一次。每次扫描，判断相比上一次宽度（长度）变化了多少，周长就加多少。扫描两次以后，周长即为所求。

注意事项

有个地方感觉很玄学，但是也很重要。离散化数组要开4倍，目前还尚不清楚原因，ORZ。。。
另外的话，HDU1828与这道题相同，但是HDU1828存在重边的情况。关于重合边，只要在排序的时候特殊处理一下就可以了。将入边排在前面，出边排在后面，就不会出现重复计算的问题了。

代码

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<bitset>
#include<stack>
#define UP(i,l,h) for(int i=l;i<h;i++)
#define DOWN(i,h,l) for(int i=h-1;i>=l;i--)
#define W(a) while(a)
#define MEM(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f3f3f3f3f
#define LL long long
#define MAXN 10010
#define SIZE 95
#define EPS 1e-10
#define MOD 1000000007
using namespace std;
struct Node {
int x1,x2,y1,y2;
int low;
Node() {}
Node(int x1,int y1,int x2,int y2,int low):x1(x1),y1(y1),x2(x2),y2(y2),low(low) {}
bool operator < (const Node b) const {
if(x1==b.x1){
return low>b.low;
}
return x1<b.x1;
}
};
Node nodes[MAXN<<1],nodes2[MAXN<<1];
int y[MAXN<<2],x[MAXN<<2];
int num[MAXN<<2],add[MAXN<<2];
int lt,rt,v;
void maintain(int o,int l,int r){
if(add[o]>0){
num[o]=y[r]-y[l-1];
}else if(l==r){
num[o]=0;
}else{
num[o]=num[o*2]+num[o*2+1];
}
}
void update(int o,int l,int r) {
if(lt<=l&&rt>=r) {
add[o]+=v;
} else {
int m=l+(r-l)/2;
if(lt<=m) {
update(o*2,l,m);
}
if(rt>m) {
update(o*2+1,m+1,r);
}
}
maintain(o,l,r);
}
int main() {
int n;
W(~scanf("%d",&n)) {
MEM(num,0);
MEM(add,0);
int m=0;
UP(i,0,n) {
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
y[m]=y1,y[m+1]=y2;
x[m]=x1,x[m+1]=x2;
nodes2[m]=Node(y1,x1,y2,x2,1);
nodes[m++]=Node(x1,y1,x2,y2,1);
nodes2[m]=Node(y2,x1,y1,x2,-1);
nodes[m++]=Node(x2,y1,x1,y2,-1);
}
int ans=0;
sort(nodes,nodes+m);
sort(y,y+m);
UP(i,0,m) {
int temp=num[1];
lt=lower_bound(y,y+m,nodes[i].y1)-y+1;
rt=lower_bound(y,y+m,nodes[i].y2)-y;
v=nodes[i].low;
update(1,1,m);
ans+=abs(num[1]-temp);
}
MEM(num,0);
MEM(add,0);
sort(nodes2,nodes2+m);
sort(x,x+m);
UP(i,0,m){
y[i]=x[i];
}
UP(i,0,m) {
int temp=num[1];
lt=lower_bound(x,x+m,nodes2[i].y1)-x+1;
rt=lower_bound(x,x+m,nodes2[i].y2)-x;
v=nodes2[i].low;
update(1,1,m);
ans+=abs(num[1]-temp);
}
printf("%dn",ans);
}
}
/*
2
0 0 1 1
0 0 -1 -1
*/

最后

以上就是矮小夕阳为你收集整理的POJ 1177 线段树+扫描线的全部内容，希望文章能够帮你解决POJ 1177 线段树+扫描线所遇到的程序开发问题。

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