Heim > Backend-Entwicklung > C++ > Hauptteil

Finden Sie die Anzahl der Punkte, die in C++ mindestens einen Punkt darüber, darunter, links oder rechts davon haben

WBOY
Freigeben: 2023-09-05 08:57:10
nach vorne
1108 Leute haben es durchsucht

Finden Sie die Anzahl der Punkte, die in C++ mindestens einen Punkt darüber, darunter, links oder rechts davon haben

In diesem Problem erhalten wir N Punkte, die sich auf einer 2D-Ebene befinden. Unsere Aufgabe besteht darin, die Anzahl der Punkte zu ermitteln, die mindestens 1 Punkt darüber, darunter, links oder rechts davon haben.

Wir müssen alle Punkte zählen, bei denen mindestens 1 Punkt 1 Punkt eine der folgenden Bedingungen erfüllt.

Der Punkt darüber− Dieser Punkt hat die gleiche X-Koordinate und eine Y-Koordinate, die um 1 größer als sein aktueller Wert ist. p>

Der Punkt darunter− Dieser Punkt hat die gleiche X-Koordinate und eine Y-Koordinate, die um 1 kleiner als sein aktueller Wert ist.

Der Punkt links davon− Dieser Punkt hat die gleiche Y-Koordinate und eine X-Koordinate, die um 1 kleiner als sein aktueller Wert ist.

Der Punkt rechts von diesem Punkt − Dieser Punkt hat die gleiche Y-Koordinate und die X-Koordinate ist um 1 größer als der aktuelle Wert.

Nehmen wir ein Beispiel, um dieses Problem zu verstehen,

Input : arr[] = {{1, 1}, {1, 0}, {0, 1}, {1, 2}, {2, 1}}
Output :1
Nach dem Login kopieren

Lösung

Um dieses Problem zu lösen, müssen wir jeden Punkt aus der Ebene nehmen und die X- und Y-Koordinaten ermitteln, die seine Nachbarpunkte maximal und minimal haben können Werte für gültiges Zählen. Wenn es innerhalb dieses Bereichs Koordinaten mit derselben X-Koordinate und einem Y-Wert gibt. Wir werden Punkte hinzufügen. Wir speichern die Anzahl in einer Variablen und geben sie zurück.

Beispiel

Nehmen wir ein Beispiel, um das Problem zu verstehen

#include <bits/stdc++.h>
using namespace std;
#define MX 2001
#define OFF 1000
struct point {
   int x, y;
};
int findPointCount(int n, struct point points[]){
   int minX[MX];
   int minY[MX];
   int maxX[MX] = { 0 };
   int maxY[MX] = { 0 };
   int xCoor, yCoor;
   fill(minX, minX + MX, INT_MAX);
   fill(minY, minY + MX, INT_MAX);
   for (int i = 0; i < n; i++) {
      points[i].x += OFF;
      points[i].y += OFF;
      xCoor = points[i].x;
      yCoor = points[i].y;
      minX[yCoor] = min(minX[yCoor], xCoor);
      maxX[yCoor] = max(maxX[yCoor], xCoor);
      minY[xCoor] = min(minY[xCoor], yCoor);
      maxY[xCoor] = max(maxY[xCoor], yCoor);
   }
   int pointCount = 0;
   for (int i = 0; i < n; i++) {
      xCoor = points[i].x;
      yCoor = points[i].y;
      if (xCoor > minX[yCoor] && xCoor < maxX[yCoor])
         if (yCoor > minY[xCoor] && yCoor < maxY[xCoor])
            pointCount++;
   }
   return pointCount;
}
int main(){
   struct point points[] = {{1, 1}, {1, 0}, {0, 1}, {1, 2}, {2, 1}};
   int n = sizeof(points) / sizeof(points[0]);
   cout<<"The number of points that have atleast one point above, below, left, right is "<<findPointCount(n, points);
}
Nach dem Login kopieren

Ausgabe

The number of points that have atleast one point above, below, left, right is 1
Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonFinden Sie die Anzahl der Punkte, die in C++ mindestens einen Punkt darüber, darunter, links oder rechts davon haben. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Verwandte Etiketten:
Quelle:tutorialspoint.com
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage