AtCoder Beginner Contest 174 B Problem "Distance" Explanation (C ++, Python, Java)

AtCoder Beginner Contest 174 B I will explain the problem "Distance".

Problem URL: https://atcoder.jp/contests/abc174/tasks/abc174_b

Problem summary

There are $ N $ points on the two-dimensional plane, and the coordinates of the $ i $ th point are $ (X_i, Y_i) $. Find out how many of these points have a distance of less than $ D $ from the origin. However, the distance between the point at the coordinates $ (p, q) $ and the origin is $ \ sqrt {p ^ 2 + q ^ 2} $.

Constraint

・ $ 1 \ leq N \ leq 2 × 10 ^ 5 $ ・ $ 0 \ leq D \ leq 2 × 10 ^ 5 $ ・|X_i|,|Y_i| \leq 2×10^5 ・ All inputs are integers

solution

For this problem, you can AC by writing code that does something like the following:

・ Enter $ N and D $ -Declare the variable $ ans $ as a counter and initialize it with 0 ・ Repeat the following $ N $ times
-Receive the information of $ (X_i, Y_i) $ and ask for $ \ sqrt {{X_i} ^ 2 + {Y_i} ^ 2} $. If it is less than $ D $, add 1 to $ ans $
・ Since $ ans $ is the number of points less than or equal to $ D $, this should be output.
(The following code is an example of the answer in 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 can be done with this code, but if you are "concerned about the error", it may be better to rewrite it as follows.

{B2.py}


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

$ \ sqrt {{x_i} ^ 2 + {y_i} ^ 2} \ leq Not D $ $ {x_i} ^ 2 + {y_i} ^ 2 \ leq D ^ 2 $ is used to determine if it is less than $ D $. From the constraint, it's $ 0 \ leq D $, so you can paraphrase </ b> the inequality condition like this: Also, a simple comparison with $ {x_i} ^ 2 + {y_i} ^ 2 $ produces less error than a simple comparison with $ \ sqrt {{x_i} ^ 2 + {y_i} ^ 2} $ (integer). Because the squares of are added together), conditional branching is possible without worrying about error </ b>.

The following is an example of the answer in C ++ and Java.

  • The code solved by ($ x_i ^ 2 + y_i ^ 2 \ leq D $)
Example solution in 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 answer example

{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);
	}
}

By the way, in C ++, the calculation time was 101ms </ b>, while in Java it was 634ms </ b>, so it is obvious that the calculation speed of C ++ is fast.

Recommended Posts