rectangle_union_area.hpp

SECTIONGeometry INCLUDEnoya/rectangle_union_area.hpp

精确计算多个半开轴对齐整数矩形的并面积；适合覆盖面积需要去除重叠的题目。

Complexity: Time: O(n log n). Space: O(n).

AC 记录：area_of_union_of_rectangles。

跳到代码 · GitHub ↗

Implementation

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(n log n).
/// Space: O(n).

#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <vector>

namespace noya {

/// @brief Exact union area of half-open axis-aligned integer rectangles by a
/// sweep line and covered-length segment tree in O(n log n).
inline __int128
rectangle_union_area(const std::vector<std::array<std::int64_t, 4>> &rec) {
  struct event {
    std::int64_t x;
    std::int64_t lo;
    std::int64_t hi;
    int dlt;
  };
  std::vector<event> ev;
  std::vector<std::int64_t> xs;
  for (auto [l, r, lo, hi] : rec) {
    assert(l <= r && lo <= hi);
    if (l == r || lo == hi) {
      continue;
    }
    ev.push_back({l, lo, hi, 1});
    ev.push_back({r, lo, hi, -1});
    xs.push_back(lo);
    xs.push_back(hi);
  }
  if (ev.empty()) {
    return 0;
  }
  std::sort(ev.begin(), ev.end(),
            [](const event &a, const event &b) { return a.x < b.x; });
  std::sort(xs.begin(), xs.end());
  xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
  int n = int(xs.size()) - 1;
  std::vector<int> cov(n * 4 + 4);
  std::vector<__int128> len(n * 4 + 4);
  auto up = [&](int nd, int l, int r) {
    if (cov[nd] > 0) {
      len[nd] = __int128(xs[r]) - xs[l];
    } else if (r - l == 1) {
      len[nd] = 0;
    } else {
      len[nd] = len[nd * 2] + len[nd * 2 + 1];
    }
  };
  auto upd = [&](auto &self, int nd, int l, int r, int ql, int qr,
                 int dlt) -> void {
    if (qr <= l || r <= ql) {
      return;
    }
    if (ql <= l && r <= qr) {
      cov[nd] += dlt;
      up(nd, l, r);
      return;
    }
    int mid = std::midpoint(l, r);
    self(self, nd * 2, l, mid, ql, qr, dlt);
    self(self, nd * 2 + 1, mid, r, ql, qr, dlt);
    up(nd, l, r);
  };

  __int128 s = 0;
  std::int64_t px = ev[0].x;
  for (int i = 0; i < int(ev.size());) {
    std::int64_t x1 = ev[i].x;
    s += (__int128(x1) - px) * len[1];
    while (i < int(ev.size()) && ev[i].x == x1) {
      int lo =
          int(std::lower_bound(xs.begin(), xs.end(), ev[i].lo) - xs.begin());
      int hi =
          int(std::lower_bound(xs.begin(), xs.end(), ev[i].hi) - xs.begin());
      upd(upd, 1, 0, n, lo, hi, ev[i].dlt);
      i++;
    }
    px = x1;
  }
  return s;
}

} // namespace noya

#ifndef NOYA_RECTANGLE_UNION_AREA_HPP
#define NOYA_RECTANGLE_UNION_AREA_HPP 1

/// @complexity Time: O(n log n).
/// Space: O(n).

#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <vector>

namespace noya {

/// @brief Exact union area of half-open axis-aligned integer rectangles by a
/// sweep line and covered-length segment tree in O(n log n).
inline __int128
rectangle_union_area(const std::vector<std::array<std::int64_t, 4>> &rec) {
  struct event {
    std::int64_t x;
    std::int64_t lo;
    std::int64_t hi;
    int dlt;
  };
  std::vector<event> ev;
  std::vector<std::int64_t> xs;
  for (auto [l, r, lo, hi] : rec) {
    assert(l <= r && lo <= hi);
    if (l == r || lo == hi) {
      continue;
    }
    ev.push_back({l, lo, hi, 1});
    ev.push_back({r, lo, hi, -1});
    xs.push_back(lo);
    xs.push_back(hi);
  }
  if (ev.empty()) {
    return 0;
  }
  std::sort(ev.begin(), ev.end(),
            [](const event &a, const event &b) { return a.x < b.x; });
  std::sort(xs.begin(), xs.end());
  xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
  int n = int(xs.size()) - 1;
  std::vector<int> cov(n * 4 + 4);
  std::vector<__int128> len(n * 4 + 4);
  auto up = [&](int nd, int l, int r) {
    if (cov[nd] > 0) {
      len[nd] = __int128(xs[r]) - xs[l];
    } else if (r - l == 1) {
      len[nd] = 0;
    } else {
      len[nd] = len[nd * 2] + len[nd * 2 + 1];
    }
  };
  auto upd = [&](auto &self, int nd, int l, int r, int ql, int qr,
                 int dlt) -> void {
    if (qr <= l || r <= ql) {
      return;
    }
    if (ql <= l && r <= qr) {
      cov[nd] += dlt;
      up(nd, l, r);
      return;
    }
    int mid = std::midpoint(l, r);
    self(self, nd * 2, l, mid, ql, qr, dlt);
    self(self, nd * 2 + 1, mid, r, ql, qr, dlt);
    up(nd, l, r);
  };

  __int128 s = 0;
  std::int64_t px = ev[0].x;
  for (int i = 0; i < int(ev.size());) {
    std::int64_t x1 = ev[i].x;
    s += (__int128(x1) - px) * len[1];
    while (i < int(ev.size()) && ev[i].x == x1) {
      int lo =
          int(std::lower_bound(xs.begin(), xs.end(), ev[i].lo) - xs.begin());
      int hi =
          int(std::lower_bound(xs.begin(), xs.end(), ev[i].hi) - xs.begin());
      upd(upd, 1, 0, n, lo, hi, ev[i].dlt);
      i++;
    }
    px = x1;
  }
  return s;
}

} // namespace noya

#endif // NOYA_RECTANGLE_UNION_AREA_HPP

#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <vector>

/// @complexity Time: O(n log n).
/// Space: O(n).

namespace noya {

/// @brief Exact union area of half-open axis-aligned integer rectangles by a
/// sweep line and covered-length segment tree in O(n log n).
inline __int128
rectangle_union_area(const std::vector<std::array<std::int64_t, 4>> &rec) {
  struct event {
    std::int64_t x;
    std::int64_t lo;
    std::int64_t hi;
    int dlt;
  };
  std::vector<event> ev;
  std::vector<std::int64_t> xs;
  for (auto [l, r, lo, hi] : rec) {
    assert(l <= r && lo <= hi);
    if (l == r || lo == hi) {
      continue;
    }
    ev.push_back({l, lo, hi, 1});
    ev.push_back({r, lo, hi, -1});
    xs.push_back(lo);
    xs.push_back(hi);
  }
  if (ev.empty()) {
    return 0;
  }
  std::sort(ev.begin(), ev.end(),
            [](const event &a, const event &b) { return a.x < b.x; });
  std::sort(xs.begin(), xs.end());
  xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
  int n = int(xs.size()) - 1;
  std::vector<int> cov(n * 4 + 4);
  std::vector<__int128> len(n * 4 + 4);
  auto up = [&](int nd, int l, int r) {
    if (cov[nd] > 0) {
      len[nd] = __int128(xs[r]) - xs[l];
    } else if (r - l == 1) {
      len[nd] = 0;
    } else {
      len[nd] = len[nd * 2] + len[nd * 2 + 1];
    }
  };
  auto upd = [&](auto &self, int nd, int l, int r, int ql, int qr,
                 int dlt) -> void {
    if (qr <= l || r <= ql) {
      return;
    }
    if (ql <= l && r <= qr) {
      cov[nd] += dlt;
      up(nd, l, r);
      return;
    }
    int mid = std::midpoint(l, r);
    self(self, nd * 2, l, mid, ql, qr, dlt);
    self(self, nd * 2 + 1, mid, r, ql, qr, dlt);
    up(nd, l, r);
  };

  __int128 s = 0;
  std::int64_t px = ev[0].x;
  for (int i = 0; i < int(ev.size());) {
    std::int64_t x1 = ev[i].x;
    s += (__int128(x1) - px) * len[1];
    while (i < int(ev.size()) && ev[i].x == x1) {
      int lo =
          int(std::lower_bound(xs.begin(), xs.end(), ev[i].lo) - xs.begin());
      int hi =
          int(std::lower_bound(xs.begin(), xs.end(), ev[i].hi) - xs.begin());
      upd(upd, 1, 0, n, lo, hi, ev[i].dlt);
      i++;
    }
    px = x1;
  }
  return s;
}

} // namespace noya