Mister雑記

競プロやります。

TopCoder SRM763 Easy 「CutCutCut」

community.topcoder.com

問題

 10,000 \times 10,000の正方形がある。 以下の形式からなる Q個のクエリに答えよ。

  • クエリは (x_1, y_1), (x_2, y_2)の2点からなる。
    • 2点は正方形の頂点を除く、異なる辺上にある。
  • 正方形にこの2点を結ぶ線分を加えたとき、正方形がいくつの領域に分割されるか求めよ。
  • ここで加えられた線分は以降のクエリでも残り続ける。

制約

  •  1 \leq Q \leq 500
  • 座標は整数かつ互いに異なる
  • 3つの線分が1点で交わることはない

考察

「正方形の辺上に点を追加」と聞いて、まず浮かんだのがこれ。 「座標を一次元に変換する」という点は使えたのだが、その後の考察でこの問題の解法に引きずられすぎてタイムロスした。

1つの線分が他の k個の線分と交わったとする。このとき線分は k + 1個に分割され、各線分が1つの面を分割する。よって k + 1個領域が増えることになる。

線分の交差判定は幾何に見えるが、正方形を数直線に展開して線分を区間とみなせば、2つの区間が交わるか否かで判定できる。 よって新しく追加された線分に対して、他の全ての線分と交差判定をすれば O(Q^2)でこの問題が解ける。

実装例

int L = 10000;

class CutCutCut {
    // 辺上の点を数直線上の点に変換
    int encode(int x, int y) {
        if (x == 0) {
            return y;
        } else if (x == L) {
            return L * 3 - y;
        } else if (y == 0) {
            return L * 4 - x;
        } else {
            return L + x;
        }
    }

public:
    vector<int> findPieces(vector<int> X1, vector<int> Y1, vector<int> X2, vector<int> Y2, int Q) {
        vector<int> in(Q), out(Q);
        vector<int> ret(Q);
        
        int ans = 1;
        for (int i = 0; i < Q; ++i) {
            int p1 = encode(X1[i], Y1[i]);
            int p2 = encode(X2[i], Y2[i]);
            if (p1 > p2) swap(p1, p2);
            in[i] = p1;
            out[i] = p2;

            ++ans;
            for (int j = 0; j < i; ++j) {
                // 交差判定
                for (int q = 0; q < 2; ++q) {
                    if (in[i] < in[j] && in[j] < out[i] && out[i] < out[j]) {
                        ++ans;
                    }
                    swap(i, j);
                }
            }
            ret[i] = ans;
        }
        return ret;
    }
};

反省

  • 焦りすぎてとても悪いムーブをしてしまった。
    • 初めてAppletを使って仕様に戸惑ったというのもある。