本文主要是介绍POJ 1177，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*
扫描线
求矩阵的周长交并
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lson (pos<<1)
#define rson (pos<<1|1)
typedef long long LL;
const int ADD = 10005;
const int maxn = 25555;
struct Seg{int a,b,h,c;Seg(int a = 0,int b = 0,int h = 0,int c = 0):a(a),b(b),h(h),c(c){};friend bool operator < (Seg p,Seg q){return p.h < q.h;}
}seg[maxn];
int cnt;
struct Node{int l,r,sum1,sum2,cover;bool left,right;int mid(){return (l + r) >> 1;}int len(){return (r - l + 1);}
}node[maxn <<2];
void pushup(int pos){if(node[pos].cover){node[pos].sum1 = node[pos].len();node[pos].sum2 = 2;node[pos].left = node[pos].right = true;}else if(node[pos].l == node[pos].r){node[pos].left = node[pos].right = false;node[pos].sum1 = node[pos].sum2 = 0;}else{node[pos].left = node[lson].left;node[pos].right = node[rson].right;node[pos].sum1 = node[lson].sum1 + node[rson].sum1;node[pos].sum2 = node[lson].sum2 + node[rson].sum2;if(node[lson].right && node[rson].left)node[pos].sum2 -= 2;}
}
void build(int l,int r,int pos){node[pos].l = l;node[pos].r = r;node[pos].cover = 0;node[pos].sum1 = node[pos].sum2 = 0;node[pos].left = node[pos].right = false;if(l == r) return;int mid = node[pos].mid();build(l,mid,lson);build(mid + 1,r,rson);
}
void update(int l,int r,int pos,int d){if(l <= node[pos].l && node[pos].r <= r){node[pos].cover += d;pushup(pos);return;}int mid = node[pos].mid();if(l <= mid)update(l,r,lson,d);if(r > mid)update(l,r,rson,d);pushup(pos);
}
int main(){int n;while(scanf("%d",&n) != EOF){cnt = 0;for(int i = 0; i < n; i++){int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);a += ADD;c += ADD;seg[cnt++] = Seg(a,c,b,1);seg[cnt++] = Seg(a,c,d,-1);}sort(seg,seg + cnt);int last = 0;LL ans = 0;build(1,21000,1);for(int i = 0; i < cnt; i++){int l = seg[i].a,r = seg[i].b, c = seg[i].c;update(l,r - 1,1,c);ans += node[1].sum2 * (seg[i + 1].h - seg[i].h);ans += abs(node[1].sum1 - last);last = node[1].sum1;}printf("%I64d\n",ans);}return 0;
}
这篇关于POJ 1177的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
