-
Notifications
You must be signed in to change notification settings - Fork 11
/
LightOJ1120.cc
109 lines (96 loc) · 2.76 KB
/
LightOJ1120.cc
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
// LightOJ 1120: Rectangle Union
// http://www.lightoj.com/volume_showproblem.php?problem=1120
//
// solution: coordinate compression + plane sweep with segment tree
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;
#define fst first
#define snd second
#define all(c) ((c).begin()), ((c).end())
vector<int> C, A, ys;
void aux(int a, int b, int c, int l, int r, int k) {
if ((a = max(a,l)) >= (b = min(b,r))) return;
if (a == l && b == r) C[k] += c;
else {
aux(a, b, c, l, (l+r)/2, 2*k+1);
aux(a, b, c, (l+r)/2, r, 2*k+2);
}
if (C[k]) A[k] = ys[r] - ys[l];
else A[k] = A[2*k+1] + A[2*k+2];
}
struct event { int l, h, c; }; // plane sweep
struct rectangle { int xl, yl, xh, yh; };
long long rectangle_area(vector<rectangle> rs) {
ys.clear();
/*
vector<int> ys; // coordinate compression
for (auto r: rs)
for (int y: {r.yl, r.yh})
ys.push_back(y);
*/
for (int i = 0; i < rs.size(); ++i) {
ys.push_back(rs[i].yl);
ys.push_back(rs[i].yh);
}
sort(all(ys)); ys.erase(unique(all(ys)), ys.end());
int n = ys.size(); // measure tree
/*
vector<int> C(4*n), A(4*n);
function<void (int,int,int,int,int,int)> aux =
[&](int a, int b, int c, int l, int r, int k) {
if ((a = max(a,l)) >= (b = min(b,r))) return;
if (a == l && b == r) C[k] += c;
else {
aux(a, b, c, l, (l+r)/2, 2*k+1);
aux(a, b, c, (l+r)/2, r, 2*k+2);
}
if (C[k]) A[k] = ys[r] - ys[l];
else A[k] = A[2*k+1] + A[2*k+2];
};
*/
C = vector<int>(8*n); A = vector<int>(8*n);
//struct event { int l, h, c; }; // plane sweep
map<int, vector<event> > sweep;
for (int i = 0; i < rs.size(); ++i) {
rectangle &r = rs[i];
// for (auto r: rs) {
int l = distance(ys.begin(), lower_bound(all(ys), r.yl));
int h = distance(ys.begin(), lower_bound(all(ys), r.yh));
sweep[r.xl].push_back((event){l, h, +1});
sweep[r.xh].push_back((event){l, h, -1});
}
long long area = 0;
long long prev = -99999999;
for (map<int,vector<event> >::iterator i = sweep.begin(); i != sweep.end(); ++i) {
area += (i->fst - prev) * A[0];
prev = i->fst;
for (int j = 0; j < i->snd.size(); ++j) {
event &e = i->snd[j];
aux(e.l,e.h,e.c,0,n,0);
}
}
/*
for (auto &p: sweep) {
area += (p.fst - prev) * A[0];
prev = p.fst;
for (auto &e: p.snd)
aux(e.l,e.h,e.c,0,n,0);
}
*/
return area;
}
int main() {
int ncase; scanf("%d", &ncase);
for (int icase = 0; icase < ncase; ++icase) {
int n; scanf("%d", &n);
vector<rectangle> rs(n);
for (int i = 0; i < n; ++i)
scanf("%d %d %d %d", &rs[i].xl, &rs[i].yl, &rs[i].xh, &rs[i].yh);
printf("Case %d: %lld\n", icase+1, rectangle_area(rs));
}
}