Cari bilangan titik yang mempunyai sekurang-kurangnya satu titik di atas, bawah, kiri atau kanannya dalam C++

Dalam masalah ini, kita diberi N mata yang terletak pada satah 2D. Tugas kami ialah untuk mencari bilangan mata yang mempunyai sekurang-kurangnya 1 mata di atas, bawah, kiri atau kanannya.

Kita perlu mengira semua mata yang mempunyai sekurang-kurangnya 1 mata 1 mata yang memenuhi mana-mana syarat berikut.

Titik di atasnya − Titik akan mempunyai koordinat X yang sama dan koordinat Y 1 lebih besar daripada nilai semasanya. p>

Titik di bawahnya − Titik akan mempunyai koordinat X yang sama dan koordinat Y 1 kurang daripada nilai semasanya.

Titik di sebelah kirinya − Titik akan mempunyai koordinat Y yang sama dan koordinat X 1 kurang daripada nilai semasanya.

Titik di sebelah kanan titik ini − Titik akan mempunyai koordinat Y yang sama dan koordinat X 1 lebih besar daripada nilai semasa.

Mari kita ambil contoh untuk memahami masalah ini,

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

Penyelesaian

#🎜🎜, Kita#Untuk menyelesaikan masalah ini perlu mengambil setiap titik dari satah dan mencari koordinat X dan Y maksimum dan minimum yang boleh dimiliki oleh titik jirannya untuk pengiraan yang cekap. Jika terdapat sebarang koordinat dengan koordinat X yang sama dan nilai Y dalam julat tersebut. Kami akan menambah mata. Kami menyimpan kiraan dalam pembolehubah dan mengembalikannya.

Contoh

Mari kita ambil contoh untuk memahami masalah

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

Output

rreee#🎜🎜

Atas ialah kandungan terperinci Cari bilangan titik yang mempunyai sekurang-kurangnya satu titik di atas, bawah, kiri atau kanannya dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!