Overview

This problem asks us to calculate the distance from a Wi-Fi router located at coordinates \((0, 0)\) to each building at coordinates \((X_i, Y_i)\), and count the total number of buildings where the distance exceeds \(D\) (i.e., the signal does not reach).

Analysis

The key to solving this problem is how to efficiently and accurately compare distances between two points.

1. Distance Calculation and Avoiding Floating-Point Arithmetic

The distance between two points can be calculated using the Euclidean distance formula \(\sqrt{X_i^2 + Y_i^2}\). The condition for the signal not reaching is \(\sqrt{X_i^2 + Y_i^2} > D\). However, computing the square root (\(\sqrt{\quad}\)) is not only relatively expensive in terms of computation cost, but also introduces the possibility of precision errors when handled as floating-point numbers (float).

Since both sides of the inequality are non-negative, squaring both sides preserves the inequality: $\(\sqrt{X_i^2 + Y_i^2} > D \iff X_i^2 + Y_i^2 > D^2\)$ By comparing the “squared values” in this way, we can perform the comparison accurately and efficiently using only integers (int).

2. Handling Large Input

In this problem, the number of buildings \(N\) can be as large as \(2 \times 10^5\), so repeatedly calling Python’s standard input() function may cause the input processing alone to exceed the time limit (TLE). By using sys.stdin.read().split() to read all input at once and processing it with an iterator or similar approach, much faster execution is possible.

Algorithm

1. Pre-compute the square of the threshold distance \(D^2\).
2. For each building’s coordinates \((X_i, Y_i)\), repeat the following:
   • Compute the squared distance from the origin \(X_i^2 + Y_i^2\).
   • If the computed value is greater than \(D^2\), increment the count by 1.
3. Output the final count.

Complexity

• Time Complexity: \(O(N)\) Since we perform one calculation and comparison for each of the \(N\) buildings, the processing completes in time proportional to the number of buildings.
• Space Complexity: \(O(N)\) Since all input is read into memory at once using sys.stdin.read(), memory consumption is proportional to the input size.

Implementation Notes

• Using map and next: For data where coordinates are arranged as \(X_1, Y_1, X_2, Y_2, \dots\), you can create an iterator with map(int, data) and use next() to extract two values at a time, concisely obtaining coordinate pairs.

• Comparing squares: Writing x * x + y * y > d_squared instead of x**2 + y**2 > d**2 avoids the overhead of the exponentiation operator, making it slightly faster.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにする
    # 大量の入力データ（N=2*10^5）を効率的に処理するために sys.stdin.read().split() を使用
    data = sys.stdin.read().split()
    if not data:
        return
    
    # 建物の数 N と 電波の届く最大距離 D を取得
    n = int(data[0])
    d = int(data[1])
    
    # 距離の比較において、計算コストの高い平方根（sqrt）を避けるため、
    # 距離の2乗（D^2）を基準値として計算する
    d_squared = d * d
    
    # 各建物の座標 (Xi, Yi) は data[2] 以降に格納されている
    # 座標データを整数のイテレータに変換する
    it = map(int, data[2:])
    
    not_reachable_count = 0
    
    # n 回ループを回し、各建物の座標を取得して判定を行う
    # x = Xi, y = Yi
    for x in it:
        try:
            y = next(it)
        except StopIteration:
            break
            
        # ユークリッド距離の2乗 (x^2 + y^2) が D^2 より大きい場合、電波は届かない
        if x * x + y * y > d_squared:
            not_reachable_count += 1
            
    # 結果を出力
    print(not_reachable_count)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.