偏角ソート の練習問題です。

本解説は前半・後半に分かれています。偏角ソートを既に知っている方は後半からお読みください。

• 前半：偏角ソートとは
• 後半：本問題の解法

---

偏角ソートとは

（原点とは異なる）点の 偏角 とは、原点からその点を見たときの方向を角度として表したものであり、 正の \(x\) 軸を基準として反時計回りに測った角度を指します。例えば、点 \((1,0)\) の偏角は \(0\degree\)、点 \((0,1)\) の偏角は \(90\degree\)、点 \((-1,-1)\) の偏角は \(225\degree\)（あるいは \(-135\degree\)）といった具合です。（なお、偏角とは本来複素数平面上の点に対して定義される語ですが、競技プログラミングにおいては通例的に普通の二次元平面上の点に対しても用いられます。）

偏角ソートとは、与えられたいくつかの点を偏角の昇順に並べ替える操作のことです。 これは本問題の表現を用いれば、\(x\) 軸正方向を向く高橋君が反時計回りに回転を始めたとき、より早く消滅する順に点をソートすることに対応します。

C++ における std::atan2 などの偏角を直接計算する関数を用いる方法もありますが、浮動小数点誤差による大小関係の誤判定を防ぐため（または高速化のため）、以下のように外積を用いる方法で偏角を比較することが一般的です。

---

1. 半平面による分類

まず、各点 \((x, y)\) がどの半平面に属するかを判定します。

• 上半平面：\(y > 0\) または ( \(y = 0\) かつ \(x > 0\) )
• 下半平面：それ以外

この判定により、偏角が \([0, 180\degree)\) に属する点と \([180\degree, 360\degree)\) に属する点とを分けることができ、偏角順の大枠が決まります。

---

2. 同一半平面内での比較

同じ半平面に属する \(2\) 点 \(A = (x_1, y_1),B = (x_2, y_2)\) については、外積 \(x_1 y_2 - y_1 x_2\) の符号によって順序を判定することができます。

• 外積 \(> 0\) のとき、\(A\) は \(B\) より偏角が小さい
• 外積 \(= 0\) のとき、\(A\) と \(B\) の偏角は等しい
• 外積 \(< 0\) のとき、\(A\) は \(B\) より偏角が大きい

\(2\) 点の偏角の比較さえできれば、あとは C++ における std::sort などの比較関数を渡せるソート関数を用いることで、偏角ソートが可能になります。

（なお、この判定法は偏角の差が \(180\degree\) 未満の時にしか用いることができません。そのため、まずは前述の通り \(2\) つの半平面に分ける必要があるのです。）

---

以上の方法により、浮動小数点演算を用いることなく、正確に偏角ソートを行うことができます。

偏角ソートの実装例 (C++) :

struct point {
    int x, y;
};

long long cross(const point &a, const point &b) {
    return (long long) a.x * b.y - (long long) a.y * b.x;
}

bool cmp(const point &a, const point &b) {
    int ah = (a.y < 0 or (a.y == 0 and a.x < 0));
    int bh = (b.y < 0 or (b.y == 0 and b.x < 0));
    if (ah != bh) return ah < bh;
    return cross(a, b) > 0;
}

void argument_sort(vector<point> &points) {
    sort(points.begin(), points.end(), cmp);
}

---

本問題の解法

基本的には偏角ソートをするだけですが、偏角が等しい点の処理のために多少の工夫が必要になります。

以下、モンスターと点を同一視します。

与えられた点を偏角ソートし、偏角の 降順 に \(1,2,\dots,N\) と番号を振り直します。

各 \(i\) について、点 \(i\) と点 \(j\) の偏角が等しいような最小の \(j\) を \(L_i\) とおきます。同様に、点 \(i\) と点 \(j\) の偏角が等しいような最大の \(j\) を \(R_i\) とおきます。このとき、\(L_i\leq i\leq R_i\) であり、点 \(L_i,L_i+1\dots,R_i\) は全て偏角が等しい点（すなわち、高橋君によって同時に消滅させられる点）です。なお、\(L_i\) は \(i\) の昇順に、\(R_i\) は \(i\) の降順に求めていくことで、全ての \(i\) に対する値を \(O(N)\) で計算可能です。

すると、\(A_j=a, B_j=b\) であるような思考実験の答えは以下のようになることが確かめられます：

• \(L_a \leq R_b\) のとき、\(R_b-L_a+1\)
• \(L_a > R_b\) のとき、\(N-L_a+1+R_b\)

よって、本問題を \(O(N\log N + Q)\) で解くことができました。

実装例 (C++) :

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct point {
    int x, y;
};

ll cross(const point &a, const point &b) {
    return (ll) a.x * b.y - (ll) a.y * b.x;
}

bool cmp(const point &a, const point &b) {
    int ah = (a.y < 0 or (a.y == 0 and a.x < 0));
    int bh = (b.y < 0 or (b.y == 0 and b.x < 0));
    if (ah != bh) return ah < bh;
    return cross(a, b) > 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<point> pt(n);
    for (int i = 0; i < n; i++) {
        cin >> pt[i].x >> pt[i].y;
    }
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) { return cmp(pt[i], pt[j]); });
    reverse(ord.begin(), ord.end());
    vector<int> rev(n);
    for (int i = 0; i < n; i++) {
        rev[ord[i]] = i;
    }
    vector<int> l(n), r(n);
    l[0] = 0, r[n - 1] = n;
    for (int i = 1; i < n; i++) {
        l[i] = (cmp(pt[ord[i]], pt[ord[i - 1]]) ? i : l[i - 1]);
    }
    for (int i = n - 2; i >= 0; i--) {
        r[i] = (cmp(pt[ord[i + 1]], pt[ord[i]]) ? i + 1 : r[i + 1]);
    }
    while (q--) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        a = l[rev[a]];
        b = r[rev[b]];
        if (a < b) cout << b - a << '\n';
        else cout << n - a + b << '\n';
    }
}