hdoj-1255 覆盖的面积

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 669 阅读时长 ≈ 2 分钟

考点

  • 扫描线

题解

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 50;
int n, ytot, ltot;
double dy[4 * maxn];

struct node1 {
  double x_, y1_, y2_, flag_;
  bool operator<(node1 &x) {
    if (x_ != x.x_) return x_ < x.x_;
    return flag_ > x.flag_;
  }
} line[2 * maxn];

struct node2 {
  // cnt_：当前区间被访问次数
  // once_：大于等于1次的长度和
  // twice_：大于等于2次的长度和
  double cnt_, once_, twice_;
} seg[4 * 2 * maxn];
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define cnt(x) seg[x].cnt_
#define once(x) seg[x].once_
#define twice(x) seg[x].twice_

void up(int rt, int l, int r) {
  once(rt) =
      cnt(rt) ? dy[r + 1] - dy[l] : (l == r ? 0 : once(lson) + once(rson));
  if (cnt(rt) > 1) {
    twice(rt) = dy[r + 1] - dy[l];
  } else if (cnt(rt) == 1) {
    twice(rt) = l == r ? 0 : once(lson) + once(rson);
  } else {
    twice(rt) = l == r ? 0 : twice(lson) + twice(rson);
  }
}

void update(int rt, int l, int r, int L, int R, int v) {
  if (L <= l && r <= R) {
    cnt(rt) += v, up(rt, l, r);
    return;
  }
  int mid = (l + r) / 2;
  if (L <= mid) update(lson, l, mid, L, R, v);
  if (R > mid) update(rson, mid + 1, r, L, R, v);
  up(rt, l, r);
}

double work() {
  cin >> n;
  double ans = 0, x1, y1, x2, y2;
  ltot = ytot = 0, memset(seg, 0, sizeof(seg));
  for (int i = 1; i <= n; ++i) {
    cin >> x1 >> y1 >> x2 >> y2;
    dy[++ytot] = y1, dy[++ytot] = y2;
    line[++ltot] = {x1, y1, y2, 1}, line[++ltot] = {x2, y1, y2, -1};
  }
  sort(dy + 1, dy + 1 + ytot), sort(line + 1, line + 1 + ltot);
  ytot = unique(dy + 1, dy + 1 + ytot) - 1 - dy;
  for (int i = 1; i < ltot; ++i) {
    y1 = lower_bound(dy + 1, dy + 1 + ytot, line[i].y1_) - dy;
    y2 = lower_bound(dy + 1, dy + 1 + ytot, line[i].y2_) - dy;
    update(1, 1, ytot - 1, y1, y2 - 1, line[i].flag_);
    ans += twice(1) * (line[i + 1].x_ - line[i].x_);
  }
  return ans;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int t;
  cin >> t;
  while (t--) cout << fixed << setprecision(2) << work() + 0.001 << endl;
  return 0;
}

思路

两个坑点：

  • 题面描述错误，给的是左下角坐标和右上角坐标
  • 最终结果要加上0.001

扫描线部分请参照矩形面积并模板，不再赘述。

设覆盖次数大于等于1的长度和为once，覆盖次数大于等于2的长度和为twice

once的情况分类如下：

  • 当前区间被覆盖任意次，once都等于当前区间长度（废话）
  • 当前区间没被覆盖，once = once(左孩子) + once(右孩子)

twice的情况分类如下：

  • 当前区间被覆盖大于等于2次，twice等于当前区间长度（显然）

  • 当前区间被覆盖等于1次，twice = once(左孩子) + once(右孩子)

    当前区间被覆盖1次之后，要想大于等于2次，肯定是再加“大于等于1”的情况。

    况且twice是once的子集，上述式子能保证情况不重不漏，

    如果改成twice = twice(左孩子) + twice(右孩子)的话，覆盖次数等于2的情况就被你忽略了。

  • 当前区间没被覆盖，twice = twice(左孩子) + twice(右孩子)