poj 1151 线段树 离散化 扫描线

发布时间:2016-12-8 13:57:38 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj 1151 线段树 离散化 扫描线",主要涉及到poj 1151 线段树 离散化 扫描线方面的内容,对于poj 1151 线段树 离散化 扫描线感兴趣的同学可以参考一下。

题目链接:http://poj.org/problem?id=1151 题目大意:在一个平面里有许多矩形,给你每个矩形两对角的坐标,求矩形面积交。 参考:http://blog.csdn.net/new_c_yuer/article/details/6013747 代码: /** 每次得到一个要更新的区间,都单点更新 */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define maxn 205 struct Line { double xl, xr, y; int tp; Line(){} Line(double xl, double xr, double y, int tp): xl(xl), xr(xr), y(y), tp(tp){} bool operator < (const Line& b)const { return y<b.y; } }line[maxn]; double x[maxn]; struct node { int l, r, tp; double sum; }v[maxn<<2]; void build(int l, int r, int n) { v[n].l = l, v[n].r = r; v[n].tp = 0; v[n].sum = 0; if (l==r) return ; int mid = (v[n].l + v[n].r) >> 1; build(l, mid, n<<1); build(mid+1, r, n<<1|1); } void update(int n, int xi, int tp) { if (v[n].l==v[n].r) { v[n].tp += tp; if (v[n].tp) v[n].sum = x[xi+1] - x[xi]; if (!v[n].tp) v[n].sum = 0; return ; } int mid = (v[n].l + v[n].r) >> 1; if (xi<=mid) update(n<<1, xi, tp); else update(n<<1|1, xi, tp); v[n].sum = v[n<<1].sum + v[n<<1|1].sum; } int main() { int n, T = 0; while (~scanf("%d", &n) && n) { int num = 0; for (int i=0; i<n; ++i) { double x1, x2, y1, y2; scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); line[++num] = Line(x1, x2, y1, -1); x[num] = x1; line[++num] = Line(x1, x2, y2, 1); x[num] = x2; } sort(x+1, x+num+1); sort(line+1, line+num+1); // for (int i=1; i<=num; ++i) // printf("%.2f ", x[i]); // printf("\n"); double ans = 0; build(1, num, 1); for (int i=1; i<=num; ++i) { int l = lower_bound(x+1, x+num+1, line[i].xl) - x; int r = lower_bound(x+1, x+num+1, line[i].xr)- x - 1; for (int j=l; j<=r; ++j) update(1, j, line[i].tp); ans += v[1].sum * (line[i+1].y - line[i].y); } printf("Test case #%d\nTotal explored area: %.2f\n\n", ++T, ans); } return 0; }/** 线段树的建立与之前的有点不同 每次得到一个要更新的区间,成段更新 */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define maxn 205 struct Line { double xr, xl, y; int tp; Line(){} Line(double xl, double xr, double y, int tp): xl(xl), xr(xr), y(y), tp(tp){} bool operator < (const Line& b)const { return y<b.y; } }line[maxn]; double x[maxn]; struct node { int l, r, tp; double sum; }v[maxn<<2]; void build(int l, int r, int n) { v[n].l = l, v[n].r = r; v[n].tp = 0; v[n].sum = 0; if (l+1==r)// return ; int mid = (l+r) >> 1; build(l, mid, n<<1);// build(mid, r, n<<1|1);// } int find(double key, int n) { int l = 1, r = n, mid; while (l<=r) { mid = (l+r) >> 1; if (x[mid]==key) return mid; else if (x[mid]>key) r = mid-1; else l = mid+1; } } void pushup(int n) { if (v[n].tp) v[n].sum = x[v[n].r] - x[v[n].l]; else if (v[n].l+1 == v[n].r) v[n].sum = 0; else v[n].sum = v[n<<1].sum + v[n<<1|1].sum; } void update(int n, int l, int r, int tp) { if (l<=v[n].l && v[n].r<=r) { v[n].tp += tp; pushup(n); return ; } int mid = (v[n].l + v[n].r) >> 1; if (r<=mid)// update(n<<1, l, r, tp); else if (l>=mid)// update(n<<1|1, l, r, tp); else { update(n<<1, l, mid, tp); update(n<<1|1, mid, r, tp); } pushup(n); } int main() { int n, T = 0; while (~scanf("%d", &n) && n) { int num = 0; for (int i=0; i<n; i++) { double x1, x2, y1, y2; scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); line[++num] = Line(x1, x2, y1, 1); x[num] = x1; line[++num] = Line(x1, x2, y2, -1); x[num] = x2; } sort(x+1, x+num+1); sort(line+1, line+num+1); build(1, num, 1); // for (int k=1; k<=2*num-1; ++k) // printf("(%d, %d) tp=%d sum=%f\n", v[k].l, v[k].r, v[k].tp, v[k].sum); double ans = 0; for (int i=1; i<num; i++) { int l = find(line[i].xl, num); int r = find(line[i].xr, num); update(1, l, r, line[i].tp); // printf("%.2f\n", v[1].sum); ans += v[1].sum * (line[i+1].y - line[i].y); } printf("Test case #%d\nTotal explored area: %.2f\n\n", ++T, ans); } return 0; }

上一篇:
下一篇:UVALive - 3971 Assemble

相关文章

相关评论