Overview

This is a problem where you determine whether each building is within distance \(D\) from the router (the origin), and count the number of buildings that cannot be reached (i.e., whose distance is greater than \(D\)).

Analysis

The Euclidean distance between a building \((X_i, Y_i)\) and the origin \((0,0)\) is \(\sqrt{X_i^2 + Y_i^2}\).
The condition for the signal not reaching a building is: - \(\sqrt{X_i^2 + Y_i^2} > D\)

However, computing the square root each time is computationally expensive, and floating-point errors may cause unstable results near the boundary (exactly at distance \(D\)).

Instead, we compare by squaring both sides. Since \(D \ge 0\), the direction of the inequality does not change: - \(\sqrt{X_i^2 + Y_i^2} > D \iff X_i^2 + Y_i^2 > D^2\)

This allows us to determine the result accurately using only integer arithmetic.

For example, when \(D=5\): - \((3,4)\) gives \(3^2+4^2=25\), which is at most \(D^2=25\), so the signal reaches - \((4,4)\) gives \(4^2+4^2=32\), which is greater than \(25\), so the signal does not reach

Also, since \(N\) is at most \(2\times 10^5\), an \(O(N)\) approach that examines each point once is both necessary and sufficient (no need to check all pairs or combinations).

Algorithm

1. Read \(N, D\) from input.
2. Precompute \(D^2\) (\(D2 = D \times D\)).
3. For each building, compute \(S = X_i^2 + Y_i^2\).
4. If \(S > D2\), the signal does not reach, so increment the count by 1.
5. Output the count at the end.

Complexity

• Time complexity: \(O(N)\) (each building is checked once)
• Space complexity: \(O(1)\) (only a constant number of variables such as the counter)

Implementation Notes

• For the comparison, do not use \(\sqrt{...}\); instead compare \(X_i^2 + Y_i^2\) with \(D^2\) (no errors and faster).

• Since \(N\) can be large, fast input methods like sys.stdin.buffer.read() are effective in Python.

• Even if coordinates are negative, squaring them causes no issues (\(x*x\) is always non-negative).

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    D = int(next(it))
    D2 = D * D

    cnt = 0
    for _ in range(N):
        x = int(next(it))
        y = int(next(it))
        if x * x + y * y > D2:
            cnt += 1

    sys.stdout.write(str(cnt))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.