AtCoder Beginner Contest 174 B Je vais expliquer le problème "Distance".
URL du problème: https://atcoder.jp/contests/abc174/tasks/abc174_b
Il y a $ N $ points sur le plan bidimensionnel, et les coordonnées du $ i $ th point sont $ (X_i, Y_i) $. Découvrez combien de ces points sont distants de moins de $ D $ de l'origine. Cependant, la distance entre le point à la coordonnée $ (p, q) $ et l'origine est $ \ sqrt {p ^ 2 + q ^ 2} $.
・ $ 1 \ leq N \ leq 2 × 10 ^ 5 $
・ $ 0 \ leq D \ leq 2 × 10 ^ 5 $
・
Pour ce problème, vous pouvez AC en écrivant du code qui fait quelque chose comme ce qui suit:
・ Entrez $ N et D $ -Déclarer la variable $ ans $ comme un compteur et l'initialiser avec 0 ・ Répétez les $ N $ suivants(Le code suivant est un exemple de la réponse en Python)・ Reçoit les informations $ (X_i, Y_i) $ et demande $ \ sqrt {{X_i} ^ 2 + {Y_i} ^ 2} $. S'il est inférieur à $ D $, ajoutez 1 à $ ans $・ Puisque $ ans $ est le nombre de points inférieur ou égal à $ D $, cela devrait être affiché.
{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 peut être fait avec ce code, mais si vous êtes "préoccupé par l'erreur", il peut être préférable de le réécrire comme suit.
{B2.py}
N,D = map(int,input().split())
ans = 0
for i in range(N):
x,y = map(int,input().split())
#Réécrire ici!!
if (x**2+y**2) <= D**2:
ans += 1
print(ans)
$ \ sqrt {{x_i} ^ 2 + {y_i} ^ 2} \ leq Pas D $ $ {x_i} ^ 2 + {y_i} ^ 2 \ leq D ^ 2 $ est utilisé pour déterminer s'il est inférieur à $ D $. À partir de la contrainte, il s'agit de $ 0 \ leq D $, vous pouvez donc paraphraser </ b> la condition de l'inégalité comme ceci. De plus, une simple comparaison avec $ {x_i} ^ 2 + {y_i} ^ 2 $ entraînera moins d'erreur qu'une simple comparaison avec $ \ sqrt {{x_i} ^ 2 + {y_i} ^ 2} $ (entier). Comme les carrés de sont additionnés), le branchement conditionnel peut être effectué sans se soucier de l ' erreur </ b>.
Voici un exemple de réponse en C ++ et Java.
{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;
}
{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);
}
}
D'ailleurs, en C ++, le temps de calcul était de 101ms </ b>, tandis qu'en Java il était de 634ms </ b>, il est donc évident que la vitesse de calcul de C ++ est rapide.
Recommended Posts