HDu 1542 Atlantis走査線矩形面積及び

Atlantis
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 20693    Accepted Submission(s): 8258  
Problem Description
There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different regions of Atlantis. Your friend Bill has to know the total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.
 
 
Input
The input file consists of several test cases. Each test case starts with a line containing a single integer n (1<=n<=100) of available maps. The n following lines describe one map each. Each of these lines contains four numbers x1;y1;x2;y2 (0<=x1 The input file is terminated by a line containing a single 0. Don’t process it.
 
 
Output
For each test case, your program should output one section. The first line of each section must be “Test case #k”, where k is the number of the test case (starting with 1). The second one must be “Total explored area: a”, where a is the total explored area (i.e. the area of the union of all rectangles in this test case), printed exact to two digits to the right of the decimal point. Output a blank line after each test case.
 
 
Sample Input

2 10 10 20 20 15 15 25 25.5 0
 
 
Sample Output

Test case #1 Total explored area: 180.00
矩形の面積を求めて
スキャンラインでは、セグメントツリーの各ノードのメンテナンス区間の長さが1つ以上のエッジで覆われています.この問題はlazyタグに対してpushdownは必要ありません.pushdownの後はメンテナンスが難しいため、pushdownはもともと操作の順序を変更するために使用されていたため、結果に影響します.順序に関係なくpushdownは必要ありません.各ノードの値は現在のノードをルートとするサブツリーを実行します.内部のすべてのlazyタグの後の値.

#include 
#include 
#include 
#include 
using namespace std;
const int N = 1e3 + 10;
#define lson o * 2, l, m
#define rson o * 2 + 1, m + 1, r
#define ls o * 2
#define rs o * 2 + 1

double sum[N * 4];
int add[N * 4];
int n;
vector  pos; 
struct line {
    double a, b, c;
    int op;
    bool operator L; 

void build(int o, int l, int r) {
    sum[o] = add[o] = 0;
    if (l == r) return;
    int m = (l + r) / 2;
    build(lson);
    build(rson);
}

void pushup(int o, int l, int r) {
    if (add[o]) sum[o] = pos[r + 1] - pos[l];
    else if (l == r) sum[o] = 0;
    else sum[o] = sum[ls] + sum[rs];
}

void update(int o, int l, int r, int L, int R, int op) {
    if (L <= l && r <= R) {
        add[o] += op;
        pushup(o, l, r);
        return;
    }
    int m = (l + r) / 2;
    if (L <= m) update(lson, L, R, op);
    if (R > m) update(rson, L, R, op);
    pushup(o, l, r);
}

int main() {
    int cas = 0;
    while (scanf("%d", &n) != EOF) {
        if (n == 0) break;
        cas++;
        pos.clear();
        L.clear();
        double a, b, c, d;
        for (int i = 1; i <= n; i++) {
            scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
            L.push_back({a, c, b, 1});
            L.push_back({a, c, d, -1});
            pos.push_back(a);
            pos.push_back(c);
        }
        sort(L.begin(), L.end());
        sort(pos.begin(), pos.end());
        pos.erase(unique(pos.begin(), pos.end()), pos.end());
        int mx = pos.size() + 5;
        build(1, 0, mx);
        double ans = 0;
        double last = 0;
        for (int i = 0; i < L.size(); i++) {
            ans += sum[1] * (L[i].c - last);
            int x = lower_bound(pos.begin(), pos.end(), L[i].a) - pos.begin();
            int y = lower_bound(pos.begin(), pos.end(), L[i].b) - pos.begin() - 1;
            update(1, 0, mx, x, y, L[i].op);
            last = L[i].c;
        }
        printf("Test case #%d
", cas);
        printf("Total explored area: %.2lf

", ans);
    }
    return 0;
}