【AtCoder】ABC 442 E - Laser Takahashi

2026-01-29

AtCoder/ABC/E問題 AtCoder/ABC/450点問題 AtCoder/水Diff AtCoder/NoviSteps/1D AtCoder/数学/偏角ソート AtCoder/累積和競技プログラミング

E - Laser Takahashi

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 1355 / NoviSteps: 1D / 配点: 450 点

問題概要

二次元平面上に $N$ 体のモンスターがいて、モンスター $i$ がいる場所の座標は $(X_i,Y_i)$ である。

この平面上の原点には高橋君が立っている。高橋君の目からは強力なレーザーが常に照射されており、高橋君が向いている方向に存在するモンスターは全て即座に消滅する。

青木君は、 $Q$ 個の独立な思考実験を行っている。 $j$ 個目の思考実験は以下の通り :

はじめ、高橋君はモンスター $A_j$ がいる方向を向いている。今から高橋君は時計回りに回転を行い、モンスター $B_j$ がいる方向を向いた瞬間に停止する。このとき、(モンスター $A_j,B_j$ を含め)合計で何体のモンスターが消滅するか？なお、モンスター $A_j,B_j$ が原点から見て同じ方向に存在する場合、高橋君は一切回転しない。

各思考実験に対する答えを求めよ。

制約

$2\leq N \leq 2\times 10^5$
$1\leq Q \leq 2\times 10^5$
$-10^9\leq X_i,Y_i \leq 10^9$
$(X_i,Y_i)\neq (0,0)$
$A_j\neq B_j$
入力は全て整数

考察

座標の正規化

この問題では、各モンスターの位置はあまり関係がなく、原点から見たときのモンスターが存在する向きのみが重要である。

したがって、まずは各モンスターの座標(位置ベクトル)を正規化し、同じ向きにあるモンスターを1つのグループにまとめることを考える。

イメージ (クリックで開く)

例えば、 $(1, 2), (2, 4), (5, 10)$ の位置に3体のモンスターが存在するとする。

これら3体は全て $y = 2x$ の直線上に存在し、原点から見たときの向きはベクトル表記で $(1, 2)^{\top}$ となる。

したがって、この3つの座標を全て $(1, 2)$ のグループに集約するというのがここでの正規化のイメージである。

これは、そのベクトルの $x, y$ 成分をそれぞれ両者の絶対値の最大公約数で割ることで実現できる(負領域にも対応するために絶対値が必要) :

(X_i^{\prime}, Y_i^{\prime}) = \left(\frac{X_i}{g}, \frac{Y_i}{g}\right) \quad \text{ただし,} \quad g = \gcd(|X_i|, |Y_i|)

※ 成分が $0$ の場合は別に場合分けが必要(実装例参照)。

以降、この左辺のベクトルを「方向ベクトル」と呼ぶことにする。

方向ベクトルを偏角でソート

次に、方向ベクトルを高橋君が回転する際に通過する順番に並べていく。

これは、各方向ベクトルに対して偏角( $x$ 軸の正方向を基準として反時計回りに測った角度)を計算し、その偏角でソートすることで実現できる。

C++では、atan2l関数を用いることで偏角を求めることができる(浮動小数点演算になるので、long doubleの範囲で計算しないと本問では WA のケースが発生する)。

その後、各方向ベクトルが所属するグループのモンスター数を累積和により前計算しておく。これにより、後述する処理で任意の偏角区間に含まれるモンスター数を $O(1)$ 時間で求められるようになる。

各思考実験への回答

最後に、各思考実験に対する答えを求めていく。 $A_j, B_j$ の方向ベクトルの偏角をそれぞれ $z_{A_j}, z_{B_j}$ 、その偏角に対応するソート済み配列でのインデックスをそれぞれ $\mathrm{idx}_{A_j}, \mathrm{idx}_{B_j}$ とする。

ここで注意したいのは、ソート済みの方向ベクトルの偏角は $-\pi \rightarrow +\pi$ の順(反時計回り)で昇順ソートされていることである。

高橋君は時計回りに回転するため、偏角が大きい方から小さい方へと向かうことになり、以下のような場合分けが必要となる。

$\mathrm{idx}_{A_j} \geq \mathrm{idx}_{B_j}$ の場合 : 単純に、 $\mathrm{idx}_{A_j}$ から $\mathrm{idx}_{B_j}$ までの区間に含まれるグループのモンスター数の和を求める。
$\mathrm{idx}_{A_j} < \mathrm{idx}_{B_j}$ の場合 : $\mathrm{idx}_{A_j}$ から先頭までと、末尾から $\mathrm{idx}_{B_j}$ までの区間に含まれるグループのモンスター数の和を求める。

後述の実装例における計算量は、座標の正規化と集計・偏角ソートに $O(N \log N)$ 時間、各思考実験の処理に $O(\log N)$ 時間かかるため、全体では $O((N+Q) \log N)$ となる。

実装例

dir_countsは、各方向ベクトルのグループに含まれるモンスター数を管理する連想配列である。

dir_to_idxは、クエリで指定されたモンスターが、unique_dirsの何番目にいるかを管理する連想配列である。ここはmapを使わずにvectorで実装してもよい(その方が計算量は良い)。

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define all(x) (x).begin(), (x).end()
5.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
6. 
7.using ll = long long;
8.using Pair_ll = pair<ll, ll>;
9. 
10.ll gcd(ll x, ll y)
11.{
12.    if (x < y)
13.        swap(x, y);
14.    ll r;
15.    while (y > 0)
16.    {
17.        r = x % y;
18.        x = y;
19.        y = r;
20.    }
21.    return x;
22.}
23. 
24.// ======================================== //
25. 
26.int main()
27.{
28.    auto norm_dir = [&](ll x, ll y) -> Pair_ll
29.    {
30.        if (x == 0 && y == 0)
31.            return {0, 0};
32.        if (x == 0)
33.            return {0, y / abs(y)};
34.        if (y == 0)
35.            return {x / abs(x), 0};
36. 
37.        ll g = gcd(abs(x), abs(y));
38.        return {x / g, y / g};
39.    };
40. 
41.    int N, Q;
42.    cin >> N >> Q;
43.    vector<Pair_ll> dirs(N);
44.    map<Pair_ll, int> dir_counts;
45.    rep(i, 0, N)
46.    {
47.        ll X, Y;
48.        cin >> X >> Y;
49.        dirs[i] = norm_dir(X, Y);
50.        dir_counts[dirs[i]]++;
51.    }
52. 
53.    vector<Pair_ll> unique_dirs;
54.    for (auto [dir, count] : dir_counts)
55.    {
56.        unique_dirs.push_back(dir);
57.    }
58.    sort(all(unique_dirs), [](Pair_ll a, Pair_ll b)
59.         { return atan2l(a.second, a.first) < atan2l(b.second, b.first); });
60. 
61.    int l = unique_dirs.size();
62.    vector<ll> ps(l + 1, 0);
63.    rep(i, 0, l) ps[i + 1] = ps[i] + dir_counts[unique_dirs[i]];
64. 
65.    map<Pair_ll, int> dir_to_idx;
66.    rep(i, 0, l)
67.        dir_to_idx[unique_dirs[i]] = i;
68. 
69.    while (Q--)
70.    {
71.        int A, B;
72.        cin >> A >> B;
73.        A--;
74.        B--;
75. 
76.        int idx_a = dir_to_idx[dirs[A]];
77.        int idx_b = dir_to_idx[dirs[B]];
78.        if (idx_a >= idx_b)
79.        {
80.            cout << ps[idx_a + 1] - ps[idx_b] << endl;
81.        }
82.        else
83.        {
84.            cout << ps[idx_a + 1] + (ps[l] - ps[idx_b]) << endl;
85.        }
86.    }
87. 
88.    return 0;
89.}