求助 POJ 1151

#include <iostream>
#include <algorithm>
#include <map>
#include <cstring>

using namespace std;

typedef long double db;

const int MAXN = 2e2 + 10;

struct Line {
    db l, r, h;
    int mark;
    Line() {}
    Line(db l, db r, db h, int mark) : l(l), r(r), h(h), mark(mark) {}
    bool operator < (const Line &p) const { return h < p.h; }
} line[MAXN << 1]; 

int tot;

db num[MAXN << 1];

struct segtree {
    int l, r, cnt;
    db len;
} t[MAXN << 2];

inline 
void pushup(int p) {
    if (t[p].cnt) t[p].len = num[t[p].r + 1] - num[t[p].l];
    else t[p].len = t[p << 1].len + t[p << 1 | 1].len;
}

void build(int l, int r, int p) {
    t[p].l = l, t[p].r = r;
    if (l == r) return ;
    int mid = l + r >> 1;
    build(l, mid, p << 1), build(mid + 1, r, p << 1 | 1);
}

void add(db l, db r, int k, int p) {
    if (num[t[p].r + 1] <= l || r <= num[t[p].l]) return ;
    if (l <= num[t[p].l] && num[t[p].r + 1] <= r) return t[p].cnt += k, pushup(p);
    add(l, r, k, p << 1), add(l, r, k, p << 1 | 1);
    pushup(p);
}

int n, c;

db ax, ay, bx, by, ans;

int main() {
    while (~scanf("%d", &n) && n) {
    	for (int i = 1; i <= n; i++) {
	        scanf("%Lf%Lf%Lf%Lf", &ax, &ay, &bx, &by);
	        num[++tot] = ax, line[tot] = Line(ax, bx, ay, 1);
	        num[++tot] = bx, line[tot] = Line(ax, bx, by, -1);
	    }
	    sort(line + 1, line + tot + 1);
	    sort(num + 1, num + tot + 1);
	    n = tot, tot = unique(num + 1, num + tot + 1) - num - 1;
	    build(1, tot - 1, 1);
	    for (int i = 1; i < n; i++) {
	        add(line[i].l, line[i].r, line[i].mark, 1);
	        ans += t[1].len * (line[i + 1].h - line[i].h);
	    }
	    printf("Test case #%d\nTotal explored area: %.2Lf\n\n", ++c, ans);
	    tot = ans = 0;
	    memset(t, 0, sizeof t);
	    memset(num, 0, sizeof num);
	    memset(line, 0, sizeof line);
	}
}