Problem: hazelnut_harvesting (2022 finals)

Boss Rob planted \(N\) happy little hazel trees in his yard (represented on a Cartesian plane). The \(i\)th tree is at integer coordinates \((X_i, Y_i)\). It's harvesting season, and Rob would like to set up some nets around the trees to collect the hazelnuts that fall.

Each net must be an axis-aligned rectangle with integer vertices (on lattice points). Rob needs at least \(1\) unit of space between nets so he can walk between them and collect the nuts. That is, nets cannot intersect, touch, or be nested. Each tree must lie strictly inside its net, i.e. must be at least \(1\) unit away from the net's edge.

Boss Rob can set up any number of nets, but would like to know the minimum total area of net required to cover all \(N\) trees.


# Constraints

\(1 \le T \le 160\)
\(1 \le N \le 800{,}000\)
\(0 \le X_i, Y_i \le 10^9\)
All \((X_i, Y_i)\) in a given test case are distinct.

\(N > 500{,}000\) in at most two test cases.
The sum of \(N\) over all test cases is at most \(4{,}000{,}000\).


# Input Format

Input begins with an integer \(T\), the number of cases. For each case, there is first a line containing a single integer \(N\). Then, \(N\) lines follow, the \(i\)th of which contains two space-separated integers \(X_i\) and \(Y_i\).


# Output Format

For the \(i\)th case, print a line containing `"Case #i: "` followed by a single integer, the minimum total area of net needed to enclose all trees according to the above requirements.


# Sample Explanation

Solutions for the first two sample cases are depicted below.

{{PHOTO_ID:2468652649959145|WIDTH:700}}

In the first case, the minimum possible net area is \(2*2 + 3*4 + 2*2 = 20\).

In the second case, the minimum possible net area is \(2*2 + 4*6 = 28\).

In the third case, it's almost possible to give each tree its own net. Unfortunately, there needs to be at least \(1\) unit of space between the nets at \((2, 2)\) so Boss Rob can walk through. This makes it indirectly necessary to use one big net to cover all trees. 

{{PHOTO_ID:504150738360453|WIDTH:700}}


Sample input:
3
4
0 0
2 1
5 0
0 6
5
10 10
12 10
8 10
5 10
8 8
4
1 1
3 3
0 4
4 6


Sample output:
Case #1: 20
Case #2: 28
Case #3: 42


Solution: First, we'll note a greedy philosophy that if we can simply use a \(2 \times 2\) square around all trees, that’d be the best solution possible. If not, the only reason why is that some pair of these squares intersects and so we are forced to union them. It turns out there is therefore no decision making that needs to happen here; we simply must find an efficient way of simulating the unions and discovering overlapping pairs.

We can maintain a set of our current answer (the answer for some prefix), and consider the next rectangle one by one. To add rectangle \(R\) (it'll initially be a \(2 \times 2\) square, but may grow), first find all rectangles that intersect \(R\). Expand \(R\)'s boundaries to include them, and then remove them from our set, and repeat. Once we find no intersections for our expanded \(R\), add it to the set, and consider the next \(2 \times 2\) square.

To do this fast, we'll need a data structure to do the following:

- Add one rectangle to the set in \(\mathcal{O}(\log^2 N)\) time
- Remove one rectangle from the set in \(\mathcal{O}(\log^2 N)\) time
- Get all rectangles whose outline intersects a query rectangle \(R\). If there are \(s\) of these, our time complexity should be at most \(\mathcal{O}(s*\log^2 N)\). This running time is affordable because any rectangle returned here will immediately be removed, so this cost can be conceptually ignored and amortized into that subsequent removal cost.

To implement this, we'll build a helper structure: a segment tree that holds all vertical lines. It will be able to query all of the \(x\) coordinates of vertical lines that intersect a given horizontal line.

The structure consists of an outer segment tree over all \(x\)'s. For a node \(n\) in the outer segment tree which is responsible for \(x\)'s in the range \([l..r]\), node \(n\) will store an implicit segment tree that can tell us all of the \(y\)'s for which there is a vertical line with an \(x\) coordinate in \([l..r]\). To answer a query for all intersecting segments in range \([l..r]\), we can walk the outer segment tree, only going down a layer if the implicit segment tree at some node tells us that we’ll find an intersecting segment by going down that path. We can make implementation a bit faster by giving a unique ID to each rectangle’s initial borders. That way we can guarantee there’s at most one rectangle with a vertical line at any particular \(x\).

This segment tree lets us add vertical lines and query horizontal ones, so we’ll create another copy of it of add horizontal lines and query vertical ones.

Using the above operations, we can repeatedly add a rectangle and union it with any rectangles which intersect *at a border*. However, there’s still one case this doesn’t catch: it’s possible that one rectangle grows quite large and then *contains* another smaller rectangle. To handle this, we can do a simple line sweep at the end to catch any rectangles that are completely inside another. Specifically, we can sweep across \(x\)'s with an event for each rectangle’s left side (start event) and right side (end event) and maintain a segment tree of which \(y\)'s are inside a rectangle. At a start event, if we’re inside a larger rectangle, then we can mark the inner rectangle as "dead" and not add its area to the answer.

This gives us a final solution that runs in \(O(N*\log^2 N)\) time and is fast enough to solve all cases even in Java.




Code: #include <algorithm>
#include <iostream>
#include <memory>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

using int64 = long long;

const int MAX_COORD = 300000;

struct Rect {
  int x1, y1, x2, y2, id;
  int mappedX1, mappedY1, mappedX2, mappedY2;
  bool ends_alive;

  Rect() {}
  Rect(int _x1, int _y1, int _x2, int _y2, int _id)
      : x1(_x1), y1(_y1), x2(_x2), y2(_y2), id(_id) {}

  bool intersects(const Rect &o) const {
    return x2 >= o.x1 && x1 <= o.x2 && y1 <= o.y2 && y2 >= o.y1;
  }

  void merge_in(const Rect &o) {
    x1 = min(x1, o.x1);
    mappedX1 = min(mappedX1, o.mappedX1);
    y1 = min(y1, o.y1);
    mappedY1 = min(mappedY1, o.mappedY1);
    x2 = max(x2, o.x2);
    mappedX2 = max(mappedX2, o.mappedX2);
    y2 = max(y2, o.y2);
    mappedY2 = max(mappedY2, o.mappedY2);
  }

  bool operator <(const Rect &o) {
    return id < o.id;
  }
};

class InnerST {
  int lo, hi, delta;
  unique_ptr<InnerST> lchild, rchild;

  void init_children() {
    if (!lchild) {
      int mid = lo + (hi - lo) / 2;
      lchild = make_unique<InnerST>(lo, mid);
      rchild = make_unique<InnerST>(mid + 1, hi);
    }
  }

 public:
  InnerST(int l, int h)
      : lo(l), hi(h), delta(0), lchild(nullptr), rchild(nullptr) {}

  void add(int l, int h, int d) {
    if (l > hi || h < lo) {
      return;
    }
    if (l <= lo && h >= hi) {
      delta += d;
      return;
    }
    init_children();
    lchild->add(l, h, d);
    rchild->add(l, h, d);
  }

  int query(int at) {
    if (lo == hi || !lchild) {
      return delta;
    }
    init_children();
    return delta + (at <= lchild->hi ? lchild : rchild)->query(at);
  }
};

class OuterST {
  int lo, hi, inner_lo, inner_hi;
  unique_ptr<OuterST> lchild, rchild;
  InnerST inner;

 public:
  OuterST(int l, int h, int inner_l, int inner_h)
      : lo(l),
        hi(h),
        inner_lo(inner_l),
        inner_hi(inner_h),
        inner(inner_l, inner_h) {
    if (lo != hi) {
      int mid = lo + (hi - lo) / 2;
      lchild = make_unique<OuterST>(lo, mid, inner_lo, inner_hi);
      rchild = make_unique<OuterST>(mid + 1, hi, inner_lo, inner_hi);
    }
  }

  // Adds a line to the inner dimension spanning inner_lo to inner_hi on
  // outer_idx
  void add_inner(int64 outer_idx, int inner_lo, int inner_hi) {
    inner.add(inner_lo, inner_hi, 1);
    if (lo != hi) {
      if (outer_idx <= lchild->hi) {
        lchild->add_inner(outer_idx, inner_lo, inner_hi);
      } else {
        rchild->add_inner(outer_idx, inner_lo, inner_hi);
      }
    }
  }

  // Queries all y's that have something here.
  vector<int> query_inner(int outer_lo, int outer_hi, int inner_idx) {
    if (outer_lo > hi || outer_hi < lo || inner.query(inner_idx) == 0)
      return {};
    if (lo == hi) {
      return {lo};
    }
    auto lres = lchild->query_inner(outer_lo, outer_hi, inner_idx);
    auto rres = rchild->query_inner(outer_lo, outer_hi, inner_idx);
    vector<int> sum(lres.size() + rres.size());
    for (int i = 0; i < (int)sum.size(); i++) {
      sum[i] = i < (int)lres.size() ? lres[i] : rres[i - lres.size()];
    }
    return sum;
  }

  void remove_inner(int outer_idx, int inner_lo, int inner_hi) {
    inner.add(inner_lo, inner_hi, -1);
    if (lo != hi) {
      if (outer_idx <= lchild->hi) {
        lchild->remove_inner(outer_idx, inner_lo, inner_hi);
      } else {
        rchild->remove_inner(outer_idx, inner_lo, inner_hi);
      }
    }
  }
};

class RectHolder {
  struct RectMapping {
    int value;
    Rect *r;
    bool v1;

    bool operator<(const RectMapping &r) const { return value < r.value; }
  };

  int sz;
  vector<int64> mapsXMajor, mapsYMajor;
  unordered_set<Rect*> aliveRects;
  OuterST xMajorST, yMajorST;
  vector<Rect*> usingXMapping, usingYMapping;
  vector<int> firstOfXMajor, lastOfXMajor;
  vector<int> firstOfYMajor, lastOfYMajor;

 public:
  RectHolder(vector<Rect> &rects)
      : sz(rects.size()),
        xMajorST(0, 2 * sz, 0, 2 * sz),
        yMajorST(0, 2 * sz, 0, 2 * sz),
        usingXMapping(2 * sz),
        usingYMapping(2 * sz),
        firstOfXMajor(2 * sz, (int)1e9),
        lastOfXMajor(2 * sz, -1),
        firstOfYMajor(2 * sz, (int)1e9),
        lastOfYMajor(2 * sz, -1) {
    vector<RectMapping> xMappings(2 * sz), yMappings(2 * sz);
    for (int i = 0; i < sz; i++) {
      xMappings[i * 2] = (RectMapping){rects[i].x1, &rects[i], true};
      xMappings[i * 2 + 1] = (RectMapping){rects[i].x2, &rects[i], false};
      yMappings[i * 2] = (RectMapping){rects[i].y1, &rects[i], true};
      yMappings[i * 2 + 1] = (RectMapping){rects[i].y2, &rects[i], false};
    }
    sort(xMappings.begin(), xMappings.end());
    sort(yMappings.begin(), yMappings.end());
    for (int i = 0; i < (int)xMappings.size(); i++) {
      usingXMapping[i] = xMappings[i].r;
      usingYMapping[i] = yMappings[i].r;
      if (xMappings[i].v1) {
        xMappings[i].r->mappedX1 = i;
        int orig = xMappings[i].r->x1;
        firstOfXMajor[orig] = min(firstOfXMajor[orig], i);
        lastOfXMajor[orig] = max(lastOfXMajor[orig], i);
      } else {
        xMappings[i].r->mappedX2 = i;
        int orig = xMappings[i].r->x2;
        firstOfXMajor[orig] = min(firstOfXMajor[orig], i);
        lastOfXMajor[orig] = max(lastOfXMajor[orig], i);
      }
      if (yMappings[i].v1) {
        yMappings[i].r->mappedY1 = i;
        int orig = yMappings[i].r->y1;
        firstOfYMajor[orig] = min(firstOfYMajor[orig], i);
        lastOfYMajor[orig] = max(lastOfYMajor[orig], i);
      } else {
        yMappings[i].r->mappedY2 = i;
        int orig = yMappings[i].r->y2;
        firstOfYMajor[orig] = min(firstOfYMajor[orig], i);
        lastOfYMajor[orig] = max(lastOfYMajor[orig], i);
      }
    }
  }

  void add_rect(Rect *r) {
    aliveRects.insert(r);
    usingXMapping[r->mappedX1] = r;
    usingXMapping[r->mappedX2] = r;
    usingYMapping[r->mappedY1] = r;
    usingYMapping[r->mappedY2] = r;
    xMajorST.add_inner(r->mappedX1, r->y1, r->y2);
    yMajorST.add_inner(r->mappedY1, r->x1, r->x2);
    xMajorST.add_inner(r->mappedX2, r->y1, r->y2);
    yMajorST.add_inner(r->mappedY2, r->x1, r->x2);
  }

  void remove_rect(Rect *r) {
    aliveRects.erase(r);
    xMajorST.remove_inner(r->mappedX1, r->y1, r->y2);
    yMajorST.remove_inner(r->mappedY1, r->x1, r->x2);
    xMajorST.remove_inner(r->mappedX2, r->y1, r->y2);
    yMajorST.remove_inner(r->mappedY2, r->x1, r->x2);
  }

  unordered_set<Rect*> get_alive_rect_intersecting(Rect *r) {
    unordered_set<Rect*> res;
    auto xsToTake1 =
        xMajorST.query_inner(firstOfXMajor[r->x1], lastOfXMajor[r->x2], r->y1);
    auto xsToTake2 =
        xMajorST.query_inner(firstOfXMajor[r->x1], lastOfXMajor[r->x2], r->y2);
    auto ysToTake1 =
        yMajorST.query_inner(firstOfYMajor[r->y1], lastOfYMajor[r->y2], r->x1);
    auto ysToTake2 =
        yMajorST.query_inner(firstOfYMajor[r->y1], lastOfYMajor[r->y2], r->x2);
    for (int x : xsToTake1) res.insert(usingXMapping[x]);
    for (int x : xsToTake2) res.insert(usingXMapping[x]);
    for (int y : ysToTake1) res.insert(usingYMapping[y]);
    for (int y : ysToTake2) res.insert(usingYMapping[y]);
    return res;
  }

  unordered_set<Rect*> get_all_alive_rects() {
    return aliveRects;
  }
};

struct Event {
  int x, y1, y2;
  bool adding;
  Rect *r;

  bool operator<(const Event &e) const {
    if (x != e.x) {
      return x < e.x;
    }
    return (y2 - y1) < (e.y2 - e.y1);
  }
};

int64 solve() {
  int N;
  vector<Rect> rects;
  vector<int> xvals, yvals;
  unordered_map<int, int> x_map, y_map, x_rev, y_rev;
  // Input.
  cin >> N;
  for (int i = 0, x, y; i < N; i++) {
    cin >> x >> y;
    rects.push_back(Rect(x - 1, y - 1, x + 1, y + 1, i));
    xvals.push_back(x - 1);
    xvals.push_back(x + 1);
    yvals.push_back(y - 1);
    yvals.push_back(y + 1);
  }
  // Compress rectangles.
  sort(xvals.begin(), xvals.end());
  xvals.resize(distance(xvals.begin(), unique(xvals.begin(), xvals.end())));
  sort(yvals.begin(), yvals.end());
  yvals.resize(distance(yvals.begin(), unique(yvals.begin(), yvals.end())));
  int i = 0;
  for (int x : xvals) {
    x_rev[i] = x;
    x_map[x] = i++;
  }
  i = 0;
  for (int y : yvals) {
    y_rev[i] = y;
    y_map[y] = i++;
  }
  for (Rect &r : rects) {
    r.x1 = x_map[r.x1];
    r.y1 = y_map[r.y1];
    r.x2 = x_map[r.x2];
    r.y2 = y_map[r.y2];
  }
  // Add to rect holder.
  RectHolder holder(rects);
  for (Rect &to_add : rects) {
    while (true) {
      auto kill_now = holder.get_alive_rect_intersecting(&to_add);
      if (kill_now.empty()) {
        break;
      }
      for (Rect *to_kill : kill_now) {
        holder.remove_rect(to_kill);
        to_add.merge_in(*to_kill);
      }
    }
    holder.add_rect(&to_add);
  }
  // Line sweep to remove any rectangles that are inside another rectangle sweep
  // left to right. On an X, process bigger then smaller.
  auto alive = holder.get_all_alive_rects();
  InnerST st(0, MAX_COORD);
  vector<Event> events;
  for (Rect *r : alive) {
    r->ends_alive = true;
    events.push_back((Event){r->x1, r->y1, r->y2, true, r});
    events.push_back((Event){r->x2, r->y1, r->y2, false, r});
  }
  sort(events.begin(), events.end());
  for (Event &e : events) {
    if (e.adding) {
      if (st.query(e.y1) == 0) {
        st.add(e.y1, e.y2, 1);
      } else {
        e.r->ends_alive = false;
      }
    } else {
      if (e.r->ends_alive) {
        st.add(e.y1, e.y2, -1);
      }
    }
  }
  // Uncompress and calculate areas.
  int64 ans = 0;
  for (const Rect &r : rects) {
    if (r.ends_alive) {
      int x1 = x_rev[r.x1], x2 = x_rev[r.x2];
      int y1 = y_rev[r.y1], y2 = y_rev[r.y2];
      ans += (int64)(x2 - x1) * (y2 - y1);
    }
  }
  return ans;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}