Rectangles [AIM Tech Round 5 (rated, Div. 1 + Div. 2) C]

http://codeforces.com/contest/1028/problem/C

N個の長方形がある。
格子点のうち、最低でもN-1個の長方形に含まれる点を1つ答えよ。

前提知識

• 累積和

考察過程

1. 最低でもN-1個というのがややこしいので、まずはN個の長方形に含まれる点を考えてみる
2. 全ての長方形に含まれるので、全ての長方形について共通部分を考えればいい
3. ある2つの長方形の共通部分は簡単なmin,max計算で求められる
4. 全ての長方形の共通部分をとれば、答えが含まれるであろう領域が出てくる
5. 問題はN-1個に含まれている点である
6. i番目の長方形以外の長方形の共通部分を高速に取りたい
7. これは[0,i)番目の長方形の共通部分と(i,N)番目の長方形の共通部分をマージすればいい
8. どちらも累積和っぽく計算できるのでいける

解法

http://codeforces.com/contest/1028/submission/42275388

長方形を扱う準備をしておく。

struct Rect {
    int L, R, U, B;
    Rect() {}
    Rect(int x1, int y1, int x2, int y2) { L = x1; U = y1; R = x2; B = y2; }
};
Rect merge(Rect a, Rect b) {
    return Rect(max(a.L, b.L), max(a.U, b.U), min(a.R, b.R), min(a.B, b.B));
}

構造体Rectは左上(L,U),右下(R,D)の長方形を指す。
mergeは2つの長方形の共通部分を取ってくる関数。
　
これで2つの長方形の共通部分の累積和を作っておこう。
pre[i] := [0,i]番目の長方形の共通部分
post[i] := [i,N)番目の長方形の共通部分
　
これでi番目以外の長方形の共通部分はmerge(pre[i-1], post[i+1])となる。
これを使えば、N-1個の長方形に含まれる頂点は探せる。
N個の長方形に含まれる頂点はN-1個の長方形に含まれる頂点の中に必ずあるので、探さなくていい。

struct Rect {
    int L, R, U, B;
    Rect() {}
    Rect(int x1, int y1, int x2, int y2) { L = x1; U = y1; R = x2; B = y2; }
};
Rect merge(Rect a, Rect b) {
    return Rect(max(a.L, b.L), max(a.U, b.U), min(a.R, b.R), min(a.B, b.B));
}
//---------------------------------------------------------------------------------------------------
int N;
Rect S[201010];
Rect pre[201010], post[201010];
pair<int, int> solve() {
    pre[0] = S[0];
    rep(i, 1, N) pre[i] = merge(pre[i - 1], S[i]);

    post[N - 1] = S[N - 1];
    rrep(i, N - 2, 0) post[i] = merge(post[i + 1], S[i]);

    rep(c, 0, N) {
        Rect s(-inf, -inf, inf, inf);
        if (c) s = merge(s, pre[c - 1]);
        if (c + 1 < N) s = merge(s, post[c + 1]);
        if (s.L <= s.R and s.U <= s.B) return { s.L, s.U };
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        S[i] = Rect(a, b, c, d);
    }

    auto ans = solve();
    printf("%d %d\n", ans.first, ans.second);
}