AtCoder Anfängerwettbewerb 174 B Problem "Entfernung" Erklärung (C ++, Python, Java)

AtCoder Beginner Contest 174 B Ich werde das Problem "Distanz" erklären.

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

Problemzusammenfassung

Es gibt $ N $ Punkte auf der zweidimensionalen Ebene und die Koordinaten des $ i $ -ten Punktes sind $ (X_i, Y_i) $. Finden Sie heraus, wie viele dieser Punkte weniger als $ D $ vom Ursprung entfernt sind. Der Abstand zwischen dem Punkt an der Koordinate $ (p, q) $ und dem Ursprung beträgt jedoch $ \ sqrt {p ^ 2 + q ^ 2} $.

Zwang

・ $ 1 \ leq N \ leq 2 × 10 ^ 5 $ ・ $ 0 \ leq D \ leq 2 × 10 ^ 5 $ ・|X_i|,|Y_i| \leq 2×10^5 ・ Alle Eingänge sind ganze Zahlen

Lösung

Für dieses Problem können Sie AC schreiben, indem Sie Code schreiben, der ungefähr Folgendes bewirkt:

・ Geben Sie $ N und D $ ein - Deklarieren Sie die Variable $ ans $ als Zähler und initialisieren Sie sie mit 0 ・ Wiederholen Sie die folgenden $ N $ Mal
・ Empfängt $ (X_i, Y_i) $ Informationen und fragt nach $ \ sqrt {{X_i} ^ 2 + {Y_i} ^ 2} $. Wenn es weniger als $ D $ ist, addieren Sie 1 zu $ ans $
・ Da $ ans $ die Anzahl der Punkte ist, die kleiner oder gleich $ D $ sind, sollte dies ausgegeben werden.
(Der folgende Code ist ein Beispiel für die Antwort 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 kann mit diesem Code durchgeführt werden. Wenn Sie jedoch "über den Fehler besorgt" sind, ist es möglicherweise besser, ihn wie folgt umzuschreiben.

{B2.py}


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

$ \ sqrt {{x_i} ^ 2 + {y_i} ^ 2} \ leq Nicht D $ $ {x_i} ^ 2 + {y_i} ^ 2 \ leq D ^ 2 $ wird verwendet, um zu bestimmen, ob es kleiner als $ D $ ist. Ausgehend von der Einschränkung ist dies $ 0 \ leq D $, sodass Sie die Bedingung der Ungleichung wie folgt umschreiben </ b> können. Ein einfacher Vergleich mit $ {x_i} ^ 2 + {y_i} ^ 2 $ führt zu weniger Fehlern als ein einfacher Vergleich mit $ \ sqrt {{x_i} ^ 2 + {y_i} ^ 2} $ (Ganzzahl). Da die Quadrate von addiert werden, kann eine bedingte Verzweigung durchgeführt werden, ohne sich um den Fehler </ b> sorgen zu müssen.

Das Folgende ist ein Beispiel für die Antwort in C ++ und Java.

  • Der Code gelöst durch ($ x_i ^ 2 + y_i ^ 2 \ leq D $)
Lösungsbeispiel 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-Antwortbeispiel

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

Übrigens betrug die Berechnungszeit in C ++ 101 ms </ b>, während sie in Java 634 ms </ b> betrug, sodass es offensichtlich ist, dass die Berechnungsgeschwindigkeit von C ++ schnell ist.

Recommended Posts