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

AtCoder Beginner Contest 174 B問題「Distance」の解説を行います。

問題URL : https://atcoder.jp/contests/abc174/tasks/abc174_b

#問題概要
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++の計算速度が速いのが一目瞭然ですね。