SRM 521 div1 med:RangeSquaredSubsets

問題

TopCoder Statistics - Problem Statement

解法

4 本の辺を全探索します。もちろん全部調べていたら (10^8)^4 で間に合わないので, 出てきた x 座標, y 座標についてのみです。

4 本の辺を決めて, その 4 本の辺に囲まれた頂点のみが正方形に囲まれるとします。すると, この頂点の選ばれ方のパターン数が答えになることがわかると思います。

では, 4 本の辺に囲まれた頂点のみが正方形に囲まれる条件は何かを求めます。
4 本の辺の長さの最大値を max とすると, max は nhigh 以下でなければなりません。
また, ある辺の長さが短すぎて細長い長方形になっている場合は, 実際に正方形を作った際に次の図のように別の 2 辺を使って囲ったほうが良いことがあります。

y 軸に平行な辺として左図にあるような辺を採用する場合, x1, x2 を使って正方形を作ろうとするとどうしても x0, x3 の辺をまたぐことになる場合, x1, x2 を採用してこれらの辺に囲まれる頂点だけを抜き取ったものは頂点数を少なく見積もってしまう可能性がある

ということで, このような可能性を排除する必要があります。

これらの条件を合わせて, 答えを求めます。

class RangeSquaredSubsets {
public:
    long long countSubsets(int nlow, int nhigh, vector <int> x, vector <int> y) {
        set<ll> S;
        vector<int> X, Y;
        X = x, Y = y;
        int n = x.size();
        sort(X.begin(), X.end());
        sort(Y.begin(), Y.end());
        for (int x1 = 0; x1 < n; x1++) for (int x2 = x1; x2 < n; x2++) {
            for (int y1 = 0; y1 < n; y1++) for (int y2 = y1; y2 < n; y2++) {
                int ma = max(X[x2]-X[x1], Y[y2]-Y[y1]);
                ma = max(ma, nlow);
                if (ma > nhigh) continue;
                if (x1 > 0 && x2 < n-1 && X[x2+1]-X[x1-1] <= ma) continue;
                if (y1 > 0 && y2 < n-1 && Y[y2+1]-Y[y1-1] <= ma) continue;
                ll flag = 0;
                for (int i = 0; i < n; i++) {
                    if (X[x1] <= x[i] && x[i] <= X[x2] && Y[y1] <= y[i] && y[i] <= Y[y2]) flag |= (1ll<<i);
                }
                if (flag) S.insert(flag);
            }
        }
        ll ret = S.size();
        return ret;
    }
};