Q003_palayutm_solution

[palayutm]

Question_ID: Q003

Language: c++

Time Cost: 40-mins

Time Complexity: O(n^2)

Solution

Merge rectangles until no two rectangles share common points.

My Code

#include <bits/stdc++.h>

using namespace std;

// tuple<u, d, l, r>
vector<tuple<int, int, int, int>> solve(vector<tuple<int, int, int, int>> a) {
  list<tuple<int, int, int, int>> li = {a.begin(), a.end()};
  for (auto it1 = li.begin(); it1 != li.end();) {
    bool ok = false;
    for (auto it2 = li.begin(); it2 != it1; it2++) {
      auto [u1, d1, l1, r1] = *it1;
      auto [u2, d2, l2, r2] = *it2;
      if (min(u1, u2) >= max(d1, d2) && min(r1, r2) >= max(l1, l2)) {  // check whether two rectangles intersect
        li.emplace_back(max(u1, u2), min(d1, d2), min(l1, l2), max(r1, r2)); //merge two rectangles, then append to list
        li.erase(it2);
        it1 = li.erase(it1);
        ok = true;
        break;
      }
    }
    if (!ok) it1++;
  }
  return {li.begin(), li.end()};
}

int main(int argc, char *argv[]) {
  int n;
  cin >> n;
  vector<tuple<int, int, int, int>> a;
  for (int i = 0; i < n; ++i) {
    int u, d, l, r;
    cin >> u >> d >> l >> r;
    a.emplace_back(u, d, l, r);
  }
  auto ans = solve(a);
  sort(ans.begin(), ans.end());
  for (auto x : ans) {
    auto [u, d, l, r] = x;
    cout << u << " " << d << " " << l << " " << r << endl;
  }
  return 0;
}

Other

g++ x.cc -std=c++17

[rbee3u]

终于看懂P巨代码了，这两重循环很nice啊。

[ryanorz]

分析了半天