Overview

This is a problem about counting the number of buildings that are located at a distance greater than \(D\) from a Wi-Fi router placed at the origin.

Analysis

Understanding the Problem

• The Wi-Fi router is installed at the origin \((0, 0)\)
• For each building \((X_i, Y_i)\), the signal reaches it if the distance from the origin is \(D\) or less
• We need to find the number of buildings where the distance is greater than \(D\)

Key Insight: Avoiding Square Root Calculations

A naive approach would be to calculate the distance \(\sqrt{X_i^2 + Y_i^2}\) for each building and compare it with \(D\).

However, square root calculations have the following issues: 1. Floating-point errors: The sqrt function returns a floating-point number, which may cause errors near boundary values 2. Computational cost: Square root calculations are relatively expensive operations

Solution: Compare by Squaring Both Sides

The comparison between distance \(d_i = \sqrt{X_i^2 + Y_i^2}\) and \(D\) gives the same result when both sides are squared (since both are non-negative).

That is: $\(\sqrt{X_i^2 + Y_i^2} > D \iff X_i^2 + Y_i^2 > D^2\)$

This allows us to compare exactly using only integers.

Concrete Example

For example, when \(D = 5\): - Building A \((3, 4)\): \(3^2 + 4^2 = 25\), \(D^2 = 25\). \(25 > 25\) is false → signal reaches - Building B \((4, 4)\): \(4^2 + 4^2 = 32\), \(D^2 = 25\). \(32 > 25\) is true → signal does not reach

Algorithm

1. Pre-calculate \(D^2\)
2. For each building \((X_i, Y_i)\):
   • Calculate \(X_i^2 + Y_i^2\)
   • If this is greater than \(D^2\), increment the count
3. Output the final count

d_squared = D × D
count = 0
for each building(X, Y):
    if X × X + Y × Y > d_squared:
        count += 1
output: count

Complexity

• Time complexity: \(O(N)\)
  • Perform constant-time calculations once for each building
• Space complexity: \(O(1)\)
  • Only use variables for the counter and coordinates

Implementation Notes

1. Pre-calculating \(D^2\): It is more efficient to calculate this once outside the loop rather than computing d * d every iteration inside the loop

2. Beware of overflow: Since the maximum values of \(X_i, Y_i\) are \(10^6\), the maximum value of \(X_i^2 + Y_i^2\) is \(2 \times 10^{12}\). Python doesn’t have integer overflow, but in C++ and similar languages, you need to use the long long type

3. Choosing the comparison operator: Since “the signal reaches if the distance is \(D\) or less”, the condition for “does not reach” is “distance is greater than \(D\)”, meaning we use > (not >=)

   Source Code

n, d = map(int, input().split())
d_squared = d * d
count = 0

for _ in range(n):
    x, y = map(int, input().split())
    if x * x + y * y > d_squared:
        count += 1

print(count)

---

This editorial was generated by claude4.5opus.