Codeforces AIM Tech Round 5 F: Make symmetrical

問題概要

以下のクエリを処理せよ。なお、以下で考慮する座標はすべて自然数座標である。

点集合に $(x, y)$ を追加する
点集合から $(x, y)$ を削除する
点 $(x, y)$ が与えられる。その時点の点集合について、原点 $(0, 0)$ と $(x, y)$ を結んでできる直線に対して線対称になるために追加すべき点の個数を求める

解説

まず重要な考察として、ある点 $p$ について考慮する際に $p$ と原点を通るような円周上で $p$ を管理するということが必要です。これは、ある 2 点 $p$ と $q$ が原点を通るような直線を軸に対象であることと、 $p$ と $q$ が同一円周上に存在することが必要十分であることによります。

以下の説明では、クエリで扱われる点の座標が $(s, t)$ であるとし、直線 $l$ に対して対称な点のペアがいくつあるかを管理する $\mathrm{cnt}(l)$ と、直線 $l$ 上に点がいくつあるかを管理する $\mathrm{onseg}(l)$ を使用しています。

クエリ 1

追加される点は、円 $x^{2} + y^{2} = C (C = s^{2} + t^{2})$ の周上に位置します。原点と $(s, t)$ を通る直線 $l'$ に対して $\mathrm{onseg}(l')$ をインクリメントし、また同一円周上に存在する他の点 $(u, v)$ それぞれに対して、原点と $(s+u, t+v)$ を通る直線 $l''$ に対して $\mathrm{cnt}(l'')$ をインクリメントすればよいです。

クエリ 2

クエリ 1 とほぼ同様の方針で処理します。対応する $\mathrm{onseg}(l')$ と $\mathrm{cnt}(l'')$ に対してデクリメントすれば良いです。

クエリ 3

直線 $l$ に対してクエリに答えるものとし、クエリが呼び出された時点で点が $N$ 個存在するとします。すでにペアになっている点対が $\mathrm{cnt}(l)$ ペアあり、直線状に位置する点が $\mathrm{onseg}(l)$ 個あるため、答えは $N - 2 \mathrm{cnt}(l) - \mathrm{onseg}(l)$ になります。

最後に、計算量を確認します。クエリ 1 及び 2 で同一円周上に位置する点全てについて操作が必要ですが、実は同一円周上に位置する点の数は十分小さいです。詳しくは Pi hiding in prime regularities - YouTube などをご覧ください (この資料は hsjoihs さんから教えていただきました。ありがとうございます)。円周ごとに独立に管理することで十分高速に処理できます。

ソースコード

直線を管理するために座標を適宜正規化して管理します。クエリで与えられる点は第一象限に属することが保証されているので、比較的容易に記述できます。

pair<int, int> normalize(int x, int y) {
    int g = __gcd(x, y);
    return make_pair(x/g, y/g);
}

signed main() {
    int Q; scanf("%lld", &Q);
    map< int, set< pair<int, int> > > points;
    map< pair<int, int>, int > cnt, on_seg;
    int whole_points = 0;
    while(Q--) {
        int t, x, y; scanf("%lld%lld%lld", &t, &x, &y);
        int sum = x*x + y*y;
        if(t == 1) {
            if(points.count(sum)) {
                for(auto p : points[sum]) {
                    int px = p.first + x;
                    int py = p.second + y;
                    cnt[normalize(px, py)]++;
                }
            }
            on_seg[normalize(x, y)]++;
            points[sum].emplace(x, y);
            whole_points++;
        }
        if(t == 2) {
            on_seg[normalize(x, y)]--;
            points[sum].erase(make_pair(x, y));
            whole_points--;
            for(auto p : points[sum]) {
                int px = p.first + x;
                int py = p.second + y;
                cnt[normalize(px, py)]--;
            }
        }
        if(t == 3) {
            auto line = normalize(x, y);
            int ans = whole_points - 2 * cnt[line] - on_seg[line];
            printf("%lld\n", ans);
        }
    }
    return 0;
}

hogecoder

tsutaj 競技プログラミングの記録