長方形から森構造を作る平面走査アルゴリズム

問題

二次平面上に軸に平行な長方形がn個与えられる。
入力として与えられる長方形について、どの二つの長方形も、

• 共通部分を持たない
• 一つの長方形がもう一つの長方形の真に内側にある

のどちらかを満たすことを保証する。

これらの長方形の包含関係から根付き有向森を作りたい。
つまり、「長方形uが長方形vを真に含む」と「森の頂点uは頂点vの先祖である」が同値となるような森。

解法

二次元の場合はx_lowでソートしてxが小さいほうから大きいほうへ平面走査する。y座標を平衡二分木で管理して親頂点を見つける。

typedef vector<int> VI;
typedef long long ValType;

struct Rect {
    ValType x_low, x_high, y_low, y_high;
};

const int MAXN = 100000;
int N;
VI G[MAXN];
Rect R[MAXN];

struct OrderIdByX {
    const Rect *p;
    OrderIdByX(const Rect *p_) { p = p_; }
    bool operator()(const int i, const int j) const {
	return p[i].x_low < p[j].x_low;
    }
};

void forest_from_rects(VI *g, const Rect *rects, int n) {
    if (n == 0) return;

    VI idx(n);
    REP (i, n) idx[i] = i;
    OrderIdByX cmp(rects);
    sort(idx.begin(), idx.end(), cmp);
    set<pair<ValType, int> > se;

    REP (i_, n) {
	int v = idx[i_], p;
	auto it = se.lower_bound(make_pair(rects[v].y_low, -1));
	while (it != se.end() && it->second != -1 && rects[it->second].x_high <= rects[v].x_low)
	    se.erase(it++);
	if (it == se.end() || it->second == -1) p = -1; // v is a root;
	else g[p = it->second].push_back(v); // rects[v] is in rects[p];
	    
	se.emplace_hint(it, rects[v].y_low, p);
	se.emplace_hint(it, rects[v].y_high, v);
    }
}

int main() {
    forest_from_rects(G, R, N);
}