题意很简单,但是周长并比面积并又稍微麻烦了一些
这时候要开一个numseg存储竖边的个数。
再开lbd,rbd分别表示边界,这样是为了帮助删除重合的边
/* ID: sdj22251 PROG: subset LANG: C++ */ #include <iostream> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <cmath> #include <ctime> #define MAXN 22222 #define MAXM 104444 #define INF 100000000 #define eps 1e-7 #define L(X) X<<1 #define R(X) X<<1|1 using namespace std; struct Seg { int l, r, h, s; Seg(){} Seg(int a, int b, int c, int d){l = a; r = b; h = c; s = d;} bool operator <(const Seg &cmp) const{ if(h == cmp.h) return s > cmp.s; return h < cmp.h; } }seg[MAXN]; struct node { int left, right, mid; int len, cnt, numseg; bool lbd, rbd; }tree[4 * MAXN]; void up(int C) { if(tree[C].cnt) { tree[C].lbd = tree[C].rbd = 1; tree[C].len = tree[C].right - tree[C].left + 1; tree[C].numseg = 2; } else if(tree[C].left == tree[C].right) tree[C].len = tree[C].numseg = tree[C].lbd = tree[C].rbd = 0; else { tree[C].lbd = tree[L(C)].lbd; tree[C].rbd = tree[R(C)].rbd; tree[C].len = tree[L(C)].len + tree[R(C)].len; tree[C].numseg = tree[L(C)].numseg + tree[R(C)].numseg; if(tree[R(C)].lbd && tree[L(C)].rbd) tree[C].numseg -= 2; } } void make_tree(int s, int e, int C) { tree[C].left = s; tree[C].right = e; tree[C].mid = (s + e) >> 1; tree[C].len = tree[C].cnt = tree[C].numseg = 0; tree[C].lbd = tree[C].rbd = 0; if(s == e) return; make_tree(s, tree[C].mid, L(C)); make_tree(tree[C].mid + 1, e, R(C)); } void update(int s, int e, int v, int C) { if(tree[C].left >= s && tree[C].right <= e) { tree[C].cnt += v; up(C); return; } if(tree[C].mid >= s) update(s, e, v, L(C)); if(tree[C].mid < e) update(s, e, v, R(C)); up(C); } int main() { int n; scanf("%d", &n); int low = 10000; int high = -10000; int m = 0; for(int i = 0; i < n; i++) { int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d); low = min(low, a); high = max(high, c); seg[m++] = Seg(a, c, b, 1); seg[m++] = Seg(a, c, d, -1); } sort(seg, seg + m); int res = 0, last = 0; make_tree(low, high, 1); for(int i = 0; i < m; i++) { if(seg[i].l < seg[i].r) update(seg[i].l, seg[i].r - 1, seg[i].s, 1); if(i < m - 1) res += tree[1].numseg * (seg[i + 1].h - seg[i].h); res += abs(tree[1].len - last); last = tree[1].len; } printf("%d\n", res); return 0; }