解題區/解題區 - POJ

POJ 1151 - Atlantis

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給一堆平行兩軸的矩形，請問面積的聯集為何。

Sample Input

1
2
3
4
2
10 10 20 20
15 15 25 25.5
0

Sample Output

1
2
Test case #1
Total explored area: 180.00

Solution

利用掃描線算法，從 x 軸小掃描到大，維度 y 軸上的覆蓋情況。

若單純用離散方法在 2D 網格上填充，算法複雜度是 $O(n^2)$，最慘情況還會再增加到 $O(n^4)$，平均上來說離散方法是可行，但是記憶體是 $O(n^2)$。

由於 ITSA 的那題 n 會高達 30000，於是拿這一題來練手，掃描線算法複雜度 $O(n \log n)$，利用線段樹操作時，維護某個區間的完全覆蓋數，當完全覆蓋數等於 0 時，則計算子樹的覆蓋長度總和，雖然沒辦法完全覆蓋，則部分覆蓋可以從子樹計算得到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <stdio.h> 
#include <string.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
const int MAXN = 262144;
class SegmentTree {
public:
    struct Node {
        int cover;				// #cover
        double L, R;			// value in real line, cover [L, R]
        double clen;			// cover length
        void init(int a = 0, double b = 0, double c = 0, double d = 0) {
            cover = a, L = b, R = c, clen = d;
        }
    } nodes[MAXN];
    double Y[MAXN];
    void pushDown(int k, int l, int r) {
    }
    void pushUp(int k, int l, int r) {
        if (nodes[k].cover > 0) {
            nodes[k].clen = nodes[k].R - nodes[k].L;
        } else {
            if (l == r)
                nodes[k].clen = 0;
            else
                nodes[k].clen = nodes[k<<1].clen + nodes[k<<1|1].clen;
        }
    }
    void build(int k, int l, int r) { 
        nodes[k].init(0, Y[l], Y[r+1], 0);
        if (l == r)
            return ;
        int mid = (l + r)/2;
        build(k<<1, l, mid);
        build(k<<1|1, mid+1, r);
        pushUp(k, l, r);
    } 
    // operator, add
    void addUpdate(int k, int l, int r, int val) {
        nodes[k].cover += val;
        if (nodes[k].cover > 0) {
            nodes[k].clen = nodes[k].R - nodes[k].L;
        } else {
            if (l == r)
                nodes[k].clen = 0;
            else
                nodes[k].clen = nodes[k<<1].clen + nodes[k<<1|1].clen;
        }
    }
    void add(int k, int l, int r, int x, int y, int val) {
        if (x <= l && r <= y) {
            addUpdate(k, l, r, val);
            return;
        }
        pushDown(k, l, r);
        int mid = (l + r)/2;
        if (x <= mid)
            add(k<<1, l, mid, x, y, val);
        if (y > mid)
            add(k<<1|1, mid+1, r, x, y, val);
        pushUp(k, l, r);
    }
    // query 
    double r_sum;
    void qinit() {
        r_sum = 0;
    }
    void query(int k, int l, int r, int x, int y) {
        if (x <= l && r <= y) {
            r_sum += nodes[k].clen;
            return ;
        }
        pushDown(k, l, r);
        int mid = (l + r)/2;
        if (x <= mid)
            query(k<<1, l, mid, x, y);
        if (y > mid)
            query(k<<1|1, mid+1, r, x, y);
        pushUp(k, l, r);
    }
} tree;
struct Event {
    double x, yl, yr;
    int val;
    Event(double a = 0, double b = 0, double c = 0, int d = 0):
    x(a), yl(b), yr(c), val(d) {}
    bool operator<(const Event &a) const {
        return x < a.x;
    }
};
double Lx[32767], Ly[32767], Rx[32767], Ry[32767], K[32767];
int N;
double areaCoverAll() {
    vector<Event> events;
    vector<double> VY;
    map<double, int> RY;
    for (int i = 0; i < N; i++) {
        double x1, x2, y1, y2;
        x1 = Lx[i], x2 = Rx[i];
        y1 = Ly[i], y2 = Ry[i];
        events.push_back(Event(x1, y1, y2,  1));
        events.push_back(Event(x2, y1, y2, -1));
        VY.push_back(y1), VY.push_back(y2);
    }
    
    sort(events.begin(), events.end());
    sort(VY.begin(), VY.end());	
    VY.resize(unique(VY.begin(), VY.end()) - VY.begin());
    
    for (int i = 0; i < VY.size(); i++) {
        tree.Y[i] = VY[i];
        RY[VY[i]] = i;
    }
    
    tree.build(1, 0, VY.size()-2);
    
    double area = 0, prevX = 0;
    for (int i = 0, j; i < events.size(); ) {		
        if (i > 0) {
            tree.qinit();
            tree.query(1, 0, VY.size()-2, 0, VY.size()-2);
            area += (events[i].x - prevX) * tree.r_sum;
        }
        j = i;
        while (j < events.size() && events[j].x <= events[i].x) {
            tree.add(1, 0, VY.size()-2, RY[events[j].yl], RY[events[j].yr] - 1, events[j].val);
            j++;
        }
        prevX = events[i].x;
        i = j;
    }
    return area;
}
int main() {
    int testcase, cases = 0;
    while (scanf("%d", &N) == 1 && N) {
        for (int i = 0; i < N; i++)
            scanf("%lf %lf %lf %lf", &Lx[i], &Ly[i], &Rx[i], &Ry[i]);
        printf("Test case #%d\n", ++cases);
        printf("Total explored area: %.2f\n", areaCoverAll());
        puts("");
    }
    return 0;
}
/*
2
10 10 20 20
15 15 25 25.5
*/