首頁  >  文章  >  後端開發  >  找到在C++中至少有一個點在其上方、下方、左方或右方的點的數量

找到在C++中至少有一個點在其上方、下方、左方或右方的點的數量

WBOY
WBOY轉載
2023-09-05 08:57:101112瀏覽

找到在C++中至少有一個點在其上方、下方、左方或右方的點的數量

在這個問題中,我們得到了位於 2D 平面上的 N 個點。我們的任務是找到其上方、下方、左側或右側至少有 1 個點的點的數量

我們需要計算所有至少有 1 個點的點1 個滿足以下任一條件的點。

其上方的點− 該點將具有相同的 X 座標,且 Y 座標比其目前值大 1。 p>

其下方的點− 該點將具有相同的 X 座標,且 Y 座標比其目前值小 1。

其左邊的點− 該點將具有相同的 Y 座標,且 X 座標比其目前值小 1。

該點右邊的點 − 該點將具有相同的Y座標和X座標比目前值大1。

讓我們舉個例子來理解這個問題,

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

解決方法

為了解決這個問題,我們需要從平面上取出每個點,並找到其相鄰點可以具有的X 和Y 座標的最大值和最小值,以進行有效計數。如果存在任何具有相同 X 座標且 Y 值在該範圍內的座標。我們將增加點數。我們將計數儲存在變數中並返回它。

範例

讓我們舉例來理解問題

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

輸出

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

以上是找到在C++中至少有一個點在其上方、下方、左方或右方的點的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:tutorialspoint.com。如有侵權,請聯絡admin@php.cn刪除