题目链接：poj1151 hdu1542
< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHByZSBjbGFzcz0="brush:java;">/*hdu 1542 Atlantis/poj 1151 Atlantis 题意：求矩形面积并 思路：将x离散化后建树(以区间建树)，将矩形分为上下两边， 上边为入边，下边为出边，从下往上扫描 注意建树使用区间建树，即线段树的节点表示的是线段，而非端点 PS：扫描线，黑书412页 */ #include
#include
#include
using namespace std; #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 const int N = 200; int cnt[N<<2];//表示该区间入边比出边多几个，有入必有出， double sum[N<<2];//代表该区间内被覆盖的线段的长度总和 double x[N<<1]; struct seg { double l, r, h; int s; seg(){} seg(double a, double b, double c, int d):l(a), r(b), h(c), s(d){} bool operator < (const seg &cmp)const { return h < cmp.h; } }ss[N]; void pushup(int l, int r, int rt) { if(cnt[rt]) sum[rt] = x[r+1] - x[l]; else if(l == r) sum[rt] = 0; else sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } void update(int L, int R, int c, int l, int r, int rt) { if(L <= l && r <= R) { cnt[rt] += c; pushup(l, r, rt); return; } int m = (l+r) >> 1; if(L <= m) update(L, R, c, lson); if(m < R) update(L, R, c, rson); pushup(l, r, rt); } int main() { int n,p = 1; while(scanf("%d",&n), n) { int m = 0; while(n--) { double x1, y1, x2, y2; scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); x[m] = x1; ss[m++] = seg(x1, x2, y1, 1);//入边标记为1 x[m] = x2; ss[m++] = seg(x1, x2, y2, -1);//出边标记为-1 } sort(x, x + m); sort(ss, ss + m); int k = 1; for(int i = 1; i < m; i ++)//去掉重复的点 if(x[i] != x[i-1]) x[k++] = x[i]; memset(sum, 0, sizeof(sum)); memset(cnt, 0, sizeof(cnt)); double ans = 0; for(int i = 0; i < m - 1; i ++) { int l = lower_bound(x, x+k, ss[i].l) - x; int r = lower_bound(x, x+k, ss[i].r) - x - 1;//因为是以区间建树，所以r应减一 if(l <= r) update(l, r, ss[i].s, 0 , k-1, 1); ans += sum[1]*(ss[i+1].h - ss[i].h); } printf("Test case #%d\nTotal explored area: %.2lf\n\n",p++,ans); } return 0; }