傳送門：
Atlantis
題意：
給定N個矩形，求總覆蓋面積
思路：
另解： 四分樹
經典的題目，在座標範圍足夠小時我們可以直接畫出矩形並計算，這題顯然無法，就跳過囉
掃描線＋線段樹＋離散化
想像有一條直線，由左向右掃過去，此時每個矩形就被兩個線段所代替
分別代表矩形開始/結束，把線段視為一個區間，於是我們丟進去線段樹維護，又因為座標值可能很醜
所以要丟進segment tree前先離散化，之後邊丟線段進去邊把答案組起來即可
大致上這樣，以下是具體步驟
- 首先將讀進來的點轉成線段儲存，依照X座標排序，相同時優先做矩形開始
- 將線段區間離散化(排序且去除重複後，重新給上1~N並記錄原本數值)
- 開始把區間丟入線段樹
- 小心維護線段樹
code:
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
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#define eps (1e-9)
#define lt(x) ((x<<1)+1)
#define rt(x) ((x<<1)+2)
#define mid(x,y) ((x+y)/2)
using namespace std;
const int MXN = 405;
struct Seg{
double u, d, pos;
bool s; //start
Seg(double a=0, double b=0, double c=0, bool d=0):
u(a), d(b), pos(c), s(d){}
bool operator < (const Seg& a)const{
return (fabs(pos-a.pos)<eps) ? (s>a.s) : (pos<a.pos);
}
}seg[MXN];
int T,I,N,dN, st[MXN * 5+5];
double x[MXN], y[MXN], ans, _x, cnt[MXN * 5 + 5];
map<double, int> lu; //lookup
void init(){
dN = 1;
ans = 0;
lu.clear();
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));
memset(seg, 0, sizeof(seg));
memset(st, 0, sizeof(st));
memset(cnt, 0, sizeof(cnt));
}
void update(int v, int l, int r, int L, int R, int flag){ //[]
if(r<=L || l>=R) return;
if(l>=L && r<=R){
st[v] += flag;
cnt[v] = ((st[v]) ? (y[r]-y[l]) : (cnt[lt(v)] + cnt[rt(v)]));
return ;
}
update(lt(v), l, mid(l,r), L, R, flag);
update(rt(v), mid(l,r), r, L, R, flag);
cnt[v] = ((st[v]) ? (y[r]-y[l]) : (cnt[lt(v)] + cnt[rt(v)]));
}
int main(){
while(scanf("%d", &N) && N){
init();
for(int i=0,j=0;i<N;i++, j=(i<<1)){
scanf("%lf %lf %lf %lf", x+j, y+j, x+(j+1), y+(j+1));
//x1 y1 x2 y2
seg[j] = Seg(y[j+1], y[j], x[j], 1);
seg[j+1] = Seg(y[j+1], y[j], x[j+1], 0);
}
N <<= 1;
sort(seg, seg+N); //線段排序
/*對y離散化開始*/
sort(y, y+N);
for(int i=1;i<N;i++)if(y[i] > y[i-1])
y[dN++] = y[i]; //unique (去除重複)
for(int i=0;i<dN;i++)
lu[y[i]] = i; //速查表
/*離散化結束*/
_x = seg[0].pos;
for(int i=0;i<N;i++){ //掃描x軸 (依x枚舉各線段)
ans += ((seg[i].pos - _x)*(cnt[0])); //目前的線段長度 * x變化
update(0, 0, dN-1, lu[seg[i].d], lu[seg[i].u], (seg[i].s)?1:-1); // 丟下個線段進去
_x = seg[i].pos;
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n", ++I, ans);
}
}