This is an exercise of polar sorting.

This editorial is two-fold. If you know about polar sorting, directly jump to the latter half.

• Former half: what is polar sorting?
• Latter half: solution of the problem

---

What is polar sorting?

The polar angle, or argument, of a given point (that is not the origin) is the direction of that point seen from the origin represented as an angle, and defined as the amount of angle measured counterclockwise from the positive \(x\)-axis direction. For example, the argument of point \((1,0)\), \((0,1)\), and \((-1,-1)\) are \(0\degree\), \(90\degree\), and \(225\degree\) (or \(-135\degree\)), respectively. (Note that “argument” is originally a concept defined for a point on the complex plane, but in competitive programming we conveniently use the term for a point on an ordinary two-dimensional plane.)

Polar sorting is a procedure to sort given points in ascending order of their arguments. In the setting of the original problem, it corresponds to sort in the order the monsters are destroyed when Takahashi is initially standing in the positive \(x\) direction and start rotating counterclockwise.

While we may use functions like std::atan2 that directly computes the argument, it is common to compare the arguments of two points using cross product.

---

1. Classification using half-plane

First, determine which half-plane each point \((x, y)\) belongs.

• Upper half-plane: \(y > 0\) or (\(y = 0\) and \(x > 0\))
• Lower half-plane: otherwise

This criteria distinguishes whether the argument falls into \([0, 180\degree)\) or \([180\degree, 360\degree)\), serving as a rough ordering by arguments.

---

2. Comparison within half-plane

For two points \(A = (x_1, y_1)\) and \(B = (x_2, y_2)\) in the same half-plane, The sign of their cross product \(x_1 y_2 - y_1 x_2\) determines the ordering:

• If (cross product) \(> 0\), then \(A\) has a smaller argument than \(B\)
• If (cross product) \(= 0\), then \(A\) has the same argument as \(B\)
• If (cross product) \(< 0\), then \(A\) has a larger argument than \(B\)

When we know how to compare the arguments of two points, we can plug it into a sort function that accepts a comparison function, like std::sort in C++, to implement polar sorting.

(Note that this comparison is valid only when the argument differs by less than \(180\degree\); that is why we first assigned points into either half-plane.)

---

This way, we can accurately perform an azimuth sorting without floating-point operations.

Sample code of azimuth sorting (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);
}

---

Solution of the original problem

Basically, we just need to perform polar sort, but we need to correctly handle points having the same argument.

From now on, we will identify monsters with points.

Sort the given points by their arguments to reassign numbers \(1,2,\dots,N\) to the points in descending order of their arguments.

For each \(i\), let \(L_i\) be the minimum \(j\) such that points \(i\) and \(j\) have the same angle. Likewise, define \(R_i\) as the maximum \(j\) such that points \(i\) and \(j\) have the same angle. Then \(L_i\leq i\leq R_i\), and points \(L_i,L_i+1\dots,R_i\) have the same argument, implying that they are all destroyed simultaneously by Takahashi. Note that \(L_i\) can be found for all \(i\) in \(O(N)\) time by scanning in ascending order of \(i\), and \(R_i\) in descending order.

Then the answer to the sought experiment with \(A_j=a\) and \(B_j=b\) can be represented as follows:

• \(R_b-L_a+1\) if \(L_a \leq R_b\)
• \(N-L_a+1+R_b\) if \(L_a > R_b\)

Therefore, the problem has been solved in a total of \(O(N\log N + Q)\) time.

Sample code (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';
    }
}