Submission #418841

#	Time	Username	Problem	Language	Result	Execution time	Memory
418841		rama_pang	Demarcation (BOI14_demarcation)	C++17	100 / 100	269 ms	31884 KiB

demarcation

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N;
  cin >> N;
  vector<array<int, 2>> A(N);
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 2; j++) {
      cin >> A[i][j];
    }
  }

  // We can make it into a tree-like structure.
  // Then, a split is = pick an edge and delete it.
  // The size of the remaining must be equal, so
  // there are only 1 option for vertical (and 1
  // for horizontal).
  //
  // To check whether they are congruent, we can make
  // a list of (length, degree) and check whether
  // some cyclic shift is equal.
  //
  // Time complexity: O(N log N).

  const auto Solve = [&](vector<array<int, 2>> A) -> pair<bool, array<int, 4>> {
    int N = A.size();
    long long area = 0;
    for (int i = 0; i < N; i++) {
      area += 1ll * A[i][0] * A[(i + 1) % N][1];
      area -= 1ll * A[i][1] * A[(i + 1) % N][0];
    }
    if (area < 0) {
      area *= -1;
      reverse(begin(A), end(A));
    }
    assert(area % 2 == 0);
    area /= 2;
    if (area % 2 == 1) { // we cannot divide by 2
      return {false, {0, 0, 0, 0}};
    }
    area /= 2;

    vector<array<int, 4>> lines;
    vector<array<int, 3>> events;
    for (int i = 0; i < N; i++) {
      auto p = A[i];
      auto q = A[(i + 1) % N];
      if (p[0] == q[0]) {
        continue;
      }
      if (p[0] < q[0]) { // bottom
        lines.push_back({p[1], +1, p[0], q[0]});
      } else { // top
        lines.push_back({p[1], -1, q[0], p[0]});
      }
    }

    vector<int> lastX(lines.size());
    for (int i = 0; i < int(lines.size()); i++) {
      events.push_back({lines[i][2], -1, i});
      events.push_back({lines[i][3], +1, i});
      lastX[i] = lines[i][2];
    }

    vector<array<int, 4>> rectangle;
    sort(begin(events), end(events));
    set<pair<array<int, 4>, int>> active;
    for (auto ev : events) {
      auto [x, type, id] = ev;

      auto top = active.lower_bound({lines[id], -1});
      auto bot = top;
      bool match = true;
      if (top == end(active)) {
        match = false;
      } else {
        if (type < 0) {
          if (bot == begin(active)) {
            match = false;
          } else {
            bot--;
          }
        } else {
          if (lines[id][1] > 0) {
            if (next(top) == end(active)){
              match = false;
            } else {
              top++;
            }
          } else {
            if (bot == begin(active)) {
              match = false;
            } else {
              bot--;
            }
          }
        }
      }

      if (match && bot->first[1] > 0 && top->first[1] < 0) {
        if (lastX[bot->second] <= x - 1 && lastX[top->second] <= x - 1) {
          assert(lastX[bot->second] == lastX[top->second]);
          rectangle.push_back({lastX[bot->second], x - 1, bot->first[0], top->first[0] - 1});
          lastX[bot->second] = lastX[top->second] = x;
        }
      }

      if (type < 0) {
        active.emplace(lines[id], id);
      } else {
        active.erase({lines[id], id});
      }
    }

    map<int, vector<array<int, 3>>> borderL;
    map<int, vector<array<int, 3>>> borderR;

    for (int id = 0; id < int(rectangle.size()); id++) {
      auto rect = rectangle[id];
      borderL[rect[0]].push_back({rect[2], rect[3], id});
      borderR[rect[1]].push_back({rect[2], rect[3], id});
    }

    for (auto &p : borderL) sort(begin(p.second), end(p.second));
    for (auto &p : borderR) sort(begin(p.second), end(p.second));

    vector<vector<int>> treeLft(rectangle.size());
    vector<vector<int>> treeRgt(rectangle.size());
    for (int id = 0; id < int(rectangle.size()); id++) {
      auto rect = rectangle[id];
      if (borderR.count(rect[0] - 1)) {
        auto &v = borderR[rect[0] - 1];
        auto it = lower_bound(begin(v), end(v), array<int, 3>{rect[3] + 1, -int(1e9), -int(1e9)});
        while (it != begin(v)) {
          it--;
          if ((*it)[1] < rect[2]) break;
          treeLft[id].emplace_back((*it)[2]);
        }
      }
      if (borderL.count(rect[1] + 1)) {
        auto &v = borderL[rect[1] + 1];
        auto it = lower_bound(begin(v), end(v), array<int, 3>{rect[3] + 1, -int(1e9), -int(1e9)});
        while (it != begin(v)) {
          it--;
          if ((*it)[1] < rect[2]) break;
          treeRgt[id].emplace_back((*it)[2]);
        }
      }
    }

    vector<array<int, 4>> cut;
    vector<long long> siz(rectangle.size());
    const auto Dfs = [&](const auto &self, int u, int p) -> void {
      for (auto v : treeLft[u]) if (v != p) {
        self(self, v, u);
        siz[u] += siz[v];
      }
      for (auto v : treeRgt[u]) if (v != p) {
        self(self, v, u);
        siz[u] += siz[v];
      }
      long long current = 1ll * (rectangle[u][1] - rectangle[u][0] + 1) * (rectangle[u][3] - rectangle[u][2] + 1);
      siz[u] += current;
    };

    const auto DfsReroot = [&](const auto &self, int u, int p) -> void {
      for (auto v : treeLft[u]) if (v != p) {
        siz[u] -= siz[v];
        siz[v] += siz[u];
        self(self, v, u);
        siz[v] -= siz[u];
        siz[u] += siz[v];
      }
      for (auto v : treeRgt[u]) if (v != p) {
        siz[u] -= siz[v];
        siz[v] += siz[u];
        self(self, v, u);
        siz[v] -= siz[u];
        siz[u] += siz[v];
      }

      long long sumLft = 0;
      long long sumRgt = 0;
      for (auto v : treeLft[u]) {
        sumLft += siz[v];
        if (siz[v] == area) {
          cut.push_back({rectangle[u][0], max(rectangle[u][2], rectangle[v][2]),
                         rectangle[u][0], min(rectangle[u][3], rectangle[v][3]) + 1});
        }
      }
      for (auto v : treeRgt[u]) {
        sumRgt += siz[v];
        if (siz[v] == area) {
          cut.push_back({rectangle[u][1] + 1, max(rectangle[u][2], rectangle[v][2]),
                         rectangle[u][1] + 1, min(rectangle[u][3], rectangle[v][3]) + 1});
        }
      }

      long long current = 1ll * (rectangle[u][1] - rectangle[u][0] + 1) * (rectangle[u][3] - rectangle[u][2] + 1);
      if (sumLft < area && sumLft + current > area) {
        long long need = area - sumLft;
        if (need % (rectangle[u][3] - rectangle[u][2] + 1) == 0) {
          need /= rectangle[u][3] - rectangle[u][2] + 1;
          assert(rectangle[u][0] + need - 1 <= rectangle[u][1]);
          cut.push_back({rectangle[u][0] + int(need), rectangle[u][2],
                         rectangle[u][0] + int(need), rectangle[u][3] + 1});
        }
      }
      if (sumRgt < area && sumRgt + current > area) {
        long long need = area - sumRgt;
        if (need % (rectangle[u][3] - rectangle[u][2] + 1) == 0) {
          need /= rectangle[u][3] - rectangle[u][2] + 1;
          assert(rectangle[u][0] + need - 1 <= rectangle[u][1]);
          cut.push_back({rectangle[u][1] + 1 - int(need), rectangle[u][2],
                         rectangle[u][1] + 1 - int(need), rectangle[u][3] + 1});
        }
      }
    };

    Dfs(Dfs, 0, -1);
    DfsReroot(DfsReroot, 0, -1);

    sort(begin(cut), end(cut));
    cut.resize(unique(begin(cut), end(cut)) - begin(cut));
    assert(cut.size() <= 1);

    if (cut.empty()) {
      return {false, {0, 0, 0, 0}};
    }

    vector<array<int, 2>> polyA;
    vector<array<int, 2>> polyB;
    vector<int> whereIs(2, -1);
    for (int i = 0; i < N; i++) {
      auto p = A[i];
      auto q = A[(i + 1) % N];
      if (p[0] == q[0]) {
        continue;
      }
      if (p[0] < q[0] && p[0] <= cut[0][0] && cut[0][0] <= q[0] && p[1] == cut[0][1]) {
        whereIs[0] = i;
      }
      if (p[0] > q[0] && q[0] <= cut[0][0] && cut[0][0] <= p[0] && p[1] == cut[0][3]) {
        whereIs[1] = i;
      }
    }
    assert(whereIs[0] != -1 && whereIs[1] != -1);
    { // Make polyA
      int cur = (whereIs[0] + 1) % N;
      while (true) {
        polyA.push_back(A[cur]);
        if (cur == whereIs[1]) {
          break;
        }
        cur = (cur + 1) % N;
      }
      polyA.push_back({cut[0][2], cut[0][3]});
      polyA.push_back({cut[0][0], cut[0][1]});
    }
    { // Make polyB
      int cur = (whereIs[1] + 1) % N;
      while (true) {
        polyB.push_back(A[cur]);
        if (cur == whereIs[0]) {
          break;
        }
        cur = (cur + 1) % N;
      }
      polyB.push_back({cut[0][0], cut[0][1]});
      polyB.push_back({cut[0][2], cut[0][3]});
    }

    const auto DeleteUselessPoints = [&](vector<array<int, 2>> poly) {
      vector<int> markBad(poly.size());
      for (int i = 0; i < int(poly.size()); i++) {
        auto p = poly[i];
        auto prv = poly[(i + poly.size() - 1) % poly.size()];
        auto nxt = poly[(i + poly.size() + 1) % poly.size()];
        if (prv[0] == p[0] && p[0] == nxt[0]) {
          markBad[i] = 1;
        }
        if (prv[1] == p[1] && p[1] == nxt[1]) {
          markBad[i] = 1;
        }
      }
      vector<array<int, 2>> newPoly;
      for (int i = 0; i < int(poly.size()); i++) {
        if (!markBad[i]) {
          newPoly.emplace_back(poly[i]);
        }
      }
      return newPoly;
    };

    polyA.resize(unique(begin(polyA), end(polyA)) - begin(polyA));
    polyB.resize(unique(begin(polyB), end(polyB)) - begin(polyB));

    polyA = DeleteUselessPoints(polyA);
    polyB = DeleteUselessPoints(polyB);

    const auto Congruent = [&]() -> bool {
      const auto MakeCanon = [&](vector<array<int, 2>> poly) {
        auto mn = poly[0];
        for (auto p : poly) {
          mn = min(mn, p);
        }
        for (int i = 0; i < int(poly.size()); i++) {
          if (poly[i] == mn) {
            vector<array<int, 2>> newPoly;
            for (int j = i; j < int(poly.size()); j++) {
              newPoly.emplace_back(poly[j]);
            }
            for (int j = 0; j < i; j++) {
              newPoly.emplace_back(poly[j]);
            }
            poly = newPoly;
            break;
          }
        }
        assert(mn == poly[0]);
        for (auto &p : poly) {
          p[0] -= mn[0];
          p[1] -= mn[1];
        }
        return poly;
      };
      polyA = MakeCanon(polyA);
      polyB = MakeCanon(polyB);
      for (int ref1 = 0; ref1 < 2; ref1++) {
        for (int ref2 = 0; ref2 < 2; ref2++) {
          for (int swp = 0; swp < 2; swp++) {
            for (int rot = 0; rot < 4; rot++) {
              if (polyA == MakeCanon(polyB)) {
                return true;
              }

              reverse(begin(polyB), end(polyB));
              if (polyA == MakeCanon(polyB)) {
                return true;
              }
              reverse(begin(polyB), end(polyB));

              for (auto &p : polyB) {
                swap(p[0], p[1]);
                p[1] *= -1;
              }
            }
            for (auto &p : polyB) {
              swap(p[0], p[1]);
            }
          }
          for (auto &p : polyB) {
            p[1] *= -1;
          }
        }
        for (auto &p : polyB) {
          p[0] *= -1;
        }
      }
      return false;
    };

    if (Congruent()) {
      return {true, cut[0]};
    } else {
      return {false, {0, 0, 0, 0}};
    }
  };

  auto ans = Solve(A);
  if (ans.first) {
    for (int i = 0; i < 4; i++) {
      cout << ans.second[i] << " \n"[i == 3];
    }
    return 0;
  }

  for (int i = 0; i < N; i++) {
    swap(A[i][0], A[i][1]);
  }
  ans = Solve(A);
  swap(ans.second[0], ans.second[1]);
  swap(ans.second[2], ans.second[3]);

  if (ans.first) {
    for (int i = 0; i < 4; i++) {
      cout << ans.second[i] << " \n"[i == 3];
    }
    return 0;
  }

  cout << "NO\n";
  return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 23 / 23
• Subtask 4: 50 / 50