hdoj-1828 Picture

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

考点

  • 扫描线

题解

见思路。

思路

本题有坑，是个多数据题目（但是竟然没告诉你），所以最外层记得再套一层循环！

由于扫描线只是一维的，而周长分为平行y轴与平行x轴两部分，先作图分析平行y轴时的扫描线变化。

能得到规律：所谓周长其实就是扫描线长度的变化量。

方法一

先算平行y轴部分的周长，再算平行x轴部分的周长，最后相加即可。

注意！若扫描线重合，应先加后减，否则会引起不必要的变化量！

假设有三根扫描线在同一位置，且长度相等，分别为{+1, -1, +1}

若先增后减，即{+1, +1, -1}，那么变化的情况为+1 -> +1 -> +1，对全局来说只有一次+1，是对的；

若先减后增，即{-1, +1, +1}，那么变化的情况为-1 -> 0 -> +1，尽管最终结果也是+1，但是凭空多了两次变化量。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e4 + 50;
int n, dtot, xtot, ytot, dis[4 * maxn];

struct node1 {
  int x_, y1_, y2_, flag_;
  bool operator<(node1 &x) {
    if (x_ != x.x_) return x_ < x.x_;
    return flag_ > x.flag_;
  }
} xl[2 * maxn], yl[2 * maxn];
// xl：垂直x轴的扫描线
// yl：垂直y轴的扫描线

struct node2 {
  ll status_, sum_;
} seg[4 * 2 * maxn];
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define stat(x) seg[x].status_
#define sum(x) seg[x].sum_

void up(int rt, int l, int r) {
  sum(rt) =
      stat(rt) ? dis[r + 1] - dis[l] : (l == r ? 0 : sum(lson) + sum(rson));
}

void update(int rt, int l, int r, int L, int R, int v) {
  if (L <= l && r <= R) {
    stat(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);
}

// 平行y轴的部分周长
ll ywork() {
  int y1, y2;
  sort(xl + 1, xl + 1 + xtot);
  ll pre = 0, ans = 0;
  for (int i = 1; i <= xtot; ++i) {
    y1 = lower_bound(dis + 1, dis + 1 + dtot, xl[i].y1_) - dis;
    y2 = lower_bound(dis + 1, dis + 1 + dtot, xl[i].y2_) - dis;
    update(1, 1, dtot - 1, y1, y2 - 1, xl[i].flag_);
    if (sum(1) != pre) ans += abs(sum(1) - pre);
    pre = sum(1);
  }
  memset(seg, 0, sizeof(seg));
  return ans;
}

// 平行x轴的部分周长
ll xwork() {
  int x1, x2;
  sort(yl + 1, yl + 1 + ytot);
  ll pre = 0, ans = 0;
  for (int i = 1; i <= ytot; ++i) {
    x1 = lower_bound(dis + 1, dis + 1 + dtot, yl[i].y1_) - dis;
    x2 = lower_bound(dis + 1, dis + 1 + dtot, yl[i].y2_) - dis;
    update(1, 1, dtot - 1, x1, x2 - 1, yl[i].flag_);
    if (sum(1) != pre) ans += abs(sum(1) - pre);
    pre = sum(1);
  }
  return ans;
}

int main() {
  while (cin >> n) {
    int x1, y1, x2, y2;
    xtot = ytot = dtot = 0, memset(seg, 0, sizeof(seg));
    for (int i = 1; i <= n; ++i) {
      cin >> x1 >> y1 >> x2 >> y2;
      xl[++xtot] = {x1, y1, y2, 1}, xl[++xtot] = {x2, y1, y2, -1};
      yl[++ytot] = {y1, x1, x2, 1}, yl[++ytot] = {y2, x1, x2, -1};
      dis[++dtot] = x1, dis[++dtot] = y1, dis[++dtot] = x2, dis[++dtot] = y2;
    }
    sort(dis + 1, dis + 1 + dtot);
    dtot = unique(dis + 1, dis + 1 + dtot) - 1 - dis;
    cout << ywork() + xwork() << endl;
  }
  return 0;
}

方法二

矩形的上下边界（平行x轴部分）受扫描线控制，所以尽管扫描线是一维的，但本题可以顺带处理二维。

扫描线彼此之间的距离已知，若知道扫描线之间的线段条数，再乘上距离就得到了这部分平行x轴的周长。

构造思路就很清楚了：

  1. 当前区间被访问过，该区间就只有两条横边（废话）
  2. 当前区间没被访问过：
    1. 当前区间的总条数等于左子区间条数+右子区间条数（上图A情况）
    2. 若左子区间的右端点、右子区间的左端点均被覆盖，说明两区间相交，当前区间的总条数应该减去2（上图B情况）
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e4 + 50;
int n, dtot, ltot, dis[4 * maxn];

struct node1 {
  int 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 {
  // vis_l：当前区间左端点是否被访问
  // vis_r：当前区间右端点是否被访问
  // cnt：有几条平行x轴
  int vis_l_, vis_r_, state_;
  ll sum_, cnt_;
} seg[4 * 2 * maxn];
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define state(x) seg[x].state_
#define sum(x) seg[x].sum_
#define visl(x) seg[x].vis_l_
#define visr(x) seg[x].vis_r_
#define cnt(x) seg[x].cnt_

void up(int rt, int l, int r) {
  if (state(rt)) {
    sum(rt) = dis[r + 1] - dis[l];
    visl(rt) = visr(rt) = 1;
    // 当前区间完全被覆盖时，肯定只有两条平行x轴
    cnt(rt) = 2;
  } else {
    if (l == r) {
      sum(rt) = 0, cnt(rt) = 0, visl(rt) = visr(rt) = 0;
    } else {
      sum(rt) = sum(lson) + sum(rson);
      cnt(rt) = cnt(lson) + cnt(rson);
      visl(rt) = visl(lson), visr(rt) = visr(rson);
      // 如果左子区间的右端点已覆盖，右子区间的左端点也覆盖
      // 说明两个子区间相交
      if (visr(lson) && visl(rson)) cnt(rt) -= 2;
    }
  }
}

void update(int rt, int l, int r, int L, int R, int v) {
  if (L <= l && r <= R) {
    state(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);
}

ll work() {
  int y1, y2;
  sort(line + 1, line + 1 + ltot);
  ll pre = 0, ans = 0;
  for (int i = 1; i < ltot; ++i) {
    y1 = lower_bound(dis + 1, dis + 1 + dtot, line[i].y1_) - dis;
    y2 = lower_bound(dis + 1, dis + 1 + dtot, line[i].y2_) - dis;
    update(1, 1, dtot - 1, y1, y2 - 1, line[i].flag_);
    if (sum(1) != pre) ans += abs(sum(1) - pre);
    pre = sum(1);
    ans += cnt(1) * (line[i + 1].x_ - line[i].x_);
  }
  // 最后一根扫描线
  y1 = lower_bound(dis + 1, dis + 1 + dtot, line[ltot].y1_) - dis;
  y2 = lower_bound(dis + 1, dis + 1 + dtot, line[ltot].y2_) - dis;
  update(1, 1, dtot - 1, y1, y2 - 1, line[ltot].flag_);
  ans += abs(sum(1) - pre);
  return ans;
}

int main() {
  while (cin >> n) {
    int x1, y1, x2, y2;
    ltot = dtot = 0, memset(seg, 0, sizeof(seg));
    for (int i = 1; i <= n; ++i) {
      cin >> x1 >> y1 >> x2 >> y2;
      dis[++dtot] = y1, dis[++dtot] = y2;
      line[++ltot] = {x1, y1, y2, 1}, line[++ltot] = {x2, y1, y2, -1};
    }
    sort(dis + 1, dis + 1 + dtot);
    dtot = unique(dis + 1, dis + 1 + dtot) - 1 - dis;
    cout << work() << endl;
  }
  return 0;
}