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

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

Ausgabe

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

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!