ABC168 F - . (Single Dot) 解説 - Baby Stepsなブログ

制約から座標圧縮をすべきであることは想像しやすいが、この問題はかなり難しいと思った。

atcoder.jp

前提

座標圧縮

pione.hatenablog.com

解説

座標圧縮を行う問題でよく見かけるパターンは以下の2つである。

いくつかの長方形が与えられて、長方形が重なる領域の面積の総和はいくつか？
いくつかの線分が与えられて、線分で区切られた領域の数はいくつか？

今回の問題は、線分が与えられてそれにより区切られた領域の面積を求めるというもので、上記の2点とは微妙に異なる。

1に類する問題は、座標圧縮後の状態をグリッドにマッピングすると、各マスと面積が対応するので対象のマスの面積をそれぞれ求めてその総和を求めればよい。

2に類する問題は、マスと線分を対応させてグリッドにマッピングし、BFSすることで求めることができる。（この時、グリッドの1マスは面積に対応しない）

今回の問題では、マスを線分に対応させつつ、移動できるマスからその面積を求める必要がある。

線分をグリッドにマッピングしたとき、線分間に空間があるかをわかるようにするため、与えられる座標を全て2倍にする。

実際にサンプル1で試すとわかるが、座標圧縮しなくても、与えられる線分の情報をそのままグリッドにマッピングすると、線分間に空間があるのかわからない。例えば、x軸方向に延びる線分で、x=0, x=1, x=2 の3つの線分をグリッドにマッピングすると、当然3行を連続して塗りつぶしてしまい、この行間に空間が存在するのかがわからない。

そのため、各座標を2倍することを考える。x=0, x=1, x=2 → x=0, x=2, x=4 このようにすると、各線分間には必ず1以上の差が生まれるため、適切に座標圧縮する（線分の座標の値+1を空白として登録する。前提参照）ことでグリッドに線分間の空間をマッピングすることができる。

グリッドのマスから面積を求める方法については結論から書くと、マス (x, y) が空白でかつ x, y が共に奇数であるマスだけを数えるようにすると良い。

あるマスが空白であるなら、そのマスの面積は (隣のY座標 - 今のY座標) * (隣のX座標 - 今のX座標) で求めることができる。

これは、前工程で線分の各座標値を2倍にし、その隣の座標を空白としたため、(x, y) のいずれかが偶数のマスは線分間の空白をマッピングするためのバッファであり、そのマスの面積は線分間の面積に対応しないため。

実装

#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define all(v) v.begin(), v.end()
using ll = long long;
template<class t> using vc=vector<t>;

template <typename T>
vector<T> compress(vector<T> &v1, vector<T> &v2, vector<T> &v3) {
  vector<T> vals;
  int n = v1.size(), m = v3.size();
  for (int i = 0; i < n; i++) {
    vals.push_back(v1[i]);
    vals.push_back(v2[i]);
    vals.push_back(v1[i] + 1);
    vals.push_back(v2[i] + 1);
  }
  for (int i = 0; i < m; i++) {
    vals.push_back(v3[i]);
    vals.push_back(v3[i] + 1);
  }
  vals.push_back(0);
  vals.push_back(1);
  sort(vals.begin(), vals.end());
  vals.erase(unique(vals.begin(), vals.end()), vals.end());
  for (int i = 0; i < n; i++) {
    v1[i] = lower_bound(vals.begin(), vals.end(), v1[i]) - vals.begin();
    v2[i] = lower_bound(vals.begin(), vals.end(), v2[i]) - vals.begin();
  }
  for (int i = 0; i < m; i++) {
    v3[i] = lower_bound(vals.begin(), vals.end(), v3[i]) - vals.begin();
  }
  return vals;
}

void inf() {
  cout << "INF" << endl;
  exit(0);
}

const ll dy[] = {0, 1, 0, -1, -1, 1, 1, -1};
const ll dx[] = {1, 0, -1, 0, 1, 1, -1, -1};

inline bool inside(ll y, ll x, ll H, ll W) {
    return (y >= 0 && x >= 0 && y < H && x < W);
}

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

  int n, m;
  cin >> n >> m;
  vc<ll> x1(n), x2(n), y1(n), x3(m), y2(m), y3(m);
  rep(i, n) cin >> x1[i] >> x2[i] >> y1[i];
  rep(i, m) cin >> x3[i] >> y2[i] >> y3[i];

  // 全ての座標の値を2倍
  rep(i, n) {
    x1[i] *= 2;
    x2[i] *= 2;
    y1[i] *= 2;
  }
  rep(i, m) {
    x3[i] *= 2;
    y2[i] *= 2;
    y3[i] *= 2;
  }

  // 座標圧縮
  auto X = compress(x1, x2, x3);
  auto Y = compress(y2, y3, y1);

  int h = X.size(), w = Y.size();

  // X軸方向、Y軸方向、別々にimos法を行う
  vc<vc<int>> g1(h, vc<int>(w)); // X軸方向
  vc<vc<int>> g2(h, vc<int>(w)); // Y軸方向

  rep(i, n) {
    g1[x1[i]][y1[i]]++;
    g1[x2[i] + 1][y1[i]]--;
  }
  rep(j, w) {
    rep(i, h - 1) { g1[i + 1][j] += g1[i][j]; }
  }
  rep(i, m) {
    g2[x3[i]][y2[i]]++;
    g2[x3[i]][y3[i] + 1]--;
  }
  rep(i, h) {
    rep(j, w - 1) { g2[i][j + 1] += g2[i][j]; }
  }

  // BFS で移動可能な領域の面積の総和を求める。h * w の範囲外に出られるなら INF
  vc<vc<bool>> visited(h, vc<bool>(w));
  queue<pair<int, int>> q;
  int sx = lower_bound(X.begin(), X.end(), 0) - X.begin();
  int sy = lower_bound(Y.begin(), Y.end(), 0) - Y.begin();
  q.emplace(sx, sy);
  visited[sx][sy] = 1;
  ll ans = 0;
  while (!q.empty()) {
    int x, y;
    tie(x, y) = q.front();
    q.pop();
    if (x % 2 == 1 and y % 2 == 1) ans += (X[x + 1] / 2 - (X[x] - 1) / 2) * (Y[y + 1] / 2 - (Y[y] - 1) / 2);
    rep(i, 4) {
      int nx = x + dx[i], ny = y + dy[i];
      if (inside(nx, ny, h, w) and g1[nx][ny] == 0 and g2[nx][ny] == 0 and visited[nx][ny] == 0) {
        visited[nx][ny] = 1;
        q.emplace(nx, ny);
      } else if (!inside(nx, ny, h, w)) {
        inf();
      }
    }
  }
  cout << ans << endl;
}