Overview

Given a Wi-Fi router located at the origin, determine the number of buildings that cannot receive the signal, where the signal reaches buildings within distance \(D\).

Analysis

Whether each building can receive the signal from the router can be determined by checking if the Euclidean distance between the building’s coordinates \((X_i, Y_i)\) and the router’s position \((0, 0)\) is at most \(D\). Specifically, the distance is calculated as \(\sqrt{X_i^2 + Y_i^2}\), but computing the square root can introduce floating-point errors. Therefore, by squaring both sides and comparing, we can make the determination more safely and efficiently: $\(X_i^2 + Y_i^2 \leq D^2\)$ We simply need to count the number of buildings that do not satisfy this inequality.

A straightforward approach of computing and comparing the distance for every building is sufficiently fast. Since \(N\) is at most \(2 \times 10^5\) in this problem, it runs within the time limit as long as each computation takes constant time.

Algorithm

1. Read \(N\) (number of buildings) and \(D\) (signal range) from the input.
2. For each building, do the following:
   • Read the coordinates \((X_i, Y_i)\).
   • Compute \(X_i^2 + Y_i^2\), and if it is greater than \(D^2\), increment the count.
3. Output the final count.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Implementation Notes

• To avoid floating-point arithmetic, distance comparisons are performed using squared values.

• By reading each coordinate sequentially and performing only the necessary computations, memory efficiency is maintained.

  Source Code

import math

# 入力の読み込み
N, D = map(int, input().split())
count = 0

for _ in range(N):
    X, Y = map(int, input().split())
    distance_squared = X**2 + Y**2
    if distance_squared > D**2:
        count += 1

print(count)

This editorial was generated by qwen3-coder-480b.