Maison  >  Article  >  développement back-end  >  Trouver le nombre de points qui ont au moins un point au-dessus, en dessous, à gauche ou à droite en C++

Trouver le nombre de points qui ont au moins un point au-dessus, en dessous, à gauche ou à droite en C++

WBOY
WBOYavant
2023-09-05 08:57:101103parcourir

Trouver le nombre de points qui ont au moins un point au-dessus, en dessous, à gauche ou à droite en C++

Dans ce problème, on nous donne N points situés sur un plan 2D. Notre tâche est de trouver le nombre de points qui ont au moins 1 point au-dessus, en dessous, à gauche ou à droite.

Nous devons compter tous les points qui ont au moins 1 point 1 point qui satisfait à l'une des conditions suivantes.

Le point au-dessus− Ce point aura la même coordonnée X et une coordonnée Y 1 supérieure à sa valeur actuelle. p>

Le point en dessous− Ce point aura la même coordonnée X et une coordonnée Y 1 inférieure à sa valeur actuelle.

Le point à sa gauche− Ce point aura la même coordonnée Y et une coordonnée X 1 inférieure à sa valeur actuelle.

Le point à droite de ce point − Ce point aura la même coordonnée Y et la même coordonnée X 1 supérieure à la valeur actuelle.

Prenons un exemple pour comprendre ce problème,

Input : arr[] = {{1, 1}, {1, 0}, {0, 1}, {1, 2}, {2, 1}}
Output :1

Solution

Pour résoudre ce problème, nous devons prendre chaque point du plan et trouver les coordonnées X et Y que ses points voisins peuvent avoir Maximum et minimum valeurs pour un comptage valide. S'il existe des coordonnées avec la même coordonnée X et une valeur Y dans cette plage. Nous ajouterons des points. Nous stockons le décompte dans une variable et le renvoyons.

Exemple

Prenons un exemple pour comprendre le problème

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

Sortie

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration:
Cet article est reproduit dans:. en cas de violation, veuillez contacter admin@php.cn Supprimer