?? 1860.cpp
字號:
/* This Code is Submitted by wywcgs for Problem 1860 on 2005-10-31 at 21:01:36 */
#include <cstdio>
#include <cstdlib>
const int MAX = 32768;
class VertLine {
public:
int u;
int d;
long long x;
bool enter;
void init(long long xa, int up, int down, bool e) {
x = xa;
u = up;
d = down;
enter = e;
}
};
class LineTree {
private:
LineTree *left;
LineTree *right;
int cover;
int x;
int y;
void updateLen() {
if(cover > 0) {
covLen = y - x;
} else if(y - x == 1) {
covLen = 0;
} else {
covLen = left->covLen + right->covLen;
}
}
public:
long long covLen;
LineTree(int l, int r) {
x = l;
y = r;
if(y != x + 1) {
int m = (x + y) / 2;
left = new LineTree(x, m);
right = new LineTree(m, y);
} else {
left = NULL;
right = NULL;
}
}
void init() {
if(left != NULL) {
left->init();
}
covLen = 0;
cover = 0;
if(right != NULL) {
right->init();
}
}
void insert(int l, int r) {
if(l <= x && y <= r) {
cover++;
} else {
if(l < (x + y) / 2) {
left->insert(l, r);
}
if(r > (x + y) / 2) {
right->insert(l, r);
}
}
updateLen();
}
void del(int l, int r) {
if(l <= x && y <= r) {
cover--;
} else {
if(l < (x + y) / 2) {
left->del(l, r);
}
if(r > (x + y) / 2) {
right->del(l, r);
}
}
updateLen();
}
};
int cmp(const void*, const void*);
int main()
{
LineTree yTree(0, MAX);
VertLine vl[2*MAX];
long long x1, y1, x2, y2;
int i, m, n;
long long area;
while(scanf("%d", &n) == 1) {
yTree.init();
for(i = 0; i < n; i++) {
scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
vl[2*i].init(x1, y2, y1, true);
vl[2*i+1].init(x2, y2, y1, false);
}
m = 2 * n;
qsort(vl, m, sizeof(VertLine), cmp);
area = 0;
yTree.insert(vl[0].d, vl[0].u);
for(i = 1; i < m; i++) {
area += (vl[i].x - vl[i-1].x) * yTree.covLen;
if(vl[i].enter) {
yTree.insert(vl[i].d, vl[i].u);
} else {
yTree.del(vl[i].d, vl[i].u);
}
}
printf("%lld\n", area);
}
return 0;
}
int cmp(const void *a, const void *b)
{
VertLine *x = (VertLine*)a, *y = (VertLine*)b;
if(x->x < y->x) {
return -1;
} else {
return 1;
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -