問題概要

2次元平面上に$N$個の点があり、$i$個目の点の座標は$(X_i , Y_i)$である。
これらのうち、原点からの距離が$D$以下であるような点は何個あるかを求めよ。
ただし、座標$(p,q)$にある点と原点との距離は$\sqrt{p^2+q^2}$である。

制約

・$1\leq N \leq 2×10^5$
・$0\leq D \leq 2×10^5$
・$|X_i|,|Y_i| \leq 2×10^5$
・入力は全て整数

解法

この問題ですが、以下のようなことを実行するコードを書けばACできます。

・$N,D$を入力する
・変数$ans$をカウンターとして宣言し、0で初期化する
・$N$回以下のことを繰り返す

・$(X_i,Y_i)$の情報を受け取り、$\sqrt{{X_i}^2+{Y_i}^2}$を求める。もしそれが$D$以下であれば$ans$に1を加算する

・$ans$が、$D$以下である点の個数なのでこれを出力すればよい

(以下のコードはPythonでの解答例です)

B.py

N,D = map(int,input().split())
ans = 0
for i in range(N):
  x,y = map(int,input().split())
  if (x**2+y**2)**0.5 <= D:
    ans += 1
print(ans)

このコードでもACは出来るのですが、"誤差を気にする"という方は以下のように書き換えた方が良いかも知れません。

B2.py

N,D = map(int,input().split())
ans = 0
for i in range(N):
  x,y = map(int,input().split())
  #ここを書き換える!!
  if (x**2+y**2) <= D**2:
    ans += 1
print(ans)

$\sqrt{{x_i}^2+{y_i}^2} \leq D$ではなく
${x_i}^2+{y_i}^2 \leq D^2$で$D$以下かどうかを判定しています。
制約より、$0 \leq D$なので、このように不等式の条件を言い換えることができます。
また、${x_i}^2+{y_i}^2$で単純に比較すると, $\sqrt{{x_i}^2+{y_i}^2}$で比較するよりも誤差があまり出ない(整数の2乗同士を足すので)ので、誤差を気にせず条件分岐することが出来ます。

以下、C++,Javaでの解答例を示します。
※($x_i^2+y_i^2 \leq D$)で解いたコードです

C++での解答例

B.cpp

include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    long long int d;
    cin >> n >> d;
    int ans = 0;
    for (int i = 0; i < n; i++){
        long long int x,y;
        cin >> x >> y;
        if (x*x+y*y <= d*d){
            ans++;
        }
    }
    cout << ans << endl;
}

Javaでの解答例

B.java

import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n;
        long d;
        n = scan.nextInt();
        d = scan.nextLong();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            long x,y;
            x = scan.nextLong();
            y = scan.nextLong();
            if (x*x+y*y <= d*d) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

ちなみに、C++では計算時間が101msだったのに対し、Javaは634msであったので、C++の計算速度が速いのが一目瞭然ですね。

AtCoder Beginner Contest 174 B問題「Distance」解説(C++,Python,Java)

問題概要

制約

解法