หาจำนวนจุดที่มีจุดอยู่ด้านบน ล่าง ซ้าย หรือขวาอย่างน้อย 1 จุดใน C++

ในปัญหานี้ เราได้รับ N จุดที่อยู่บนระนาบ 2 มิติ งานของเราคือ การหาจำนวนจุดที่มีจุดอื่นอยู่ด้านบน ล่าง ซ้าย หรือขวาอย่างน้อย 1 จุด

เราต้องนับจุดทั้งหมดที่มีจุดอื่นอย่างน้อย 1 จุดที่ตรงตามเงื่อนไขใดเงื่อนไขหนึ่ง:

• จุดด้านบน − มีพิกัด X เดียวกัน และพิกัด Y มากกว่า 1 หน่วย
• จุดด้านล่าง − มีพิกัด 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 อยู่ในช่วงระหว่าง minY และ maxY และมีจุดที่มีพิกัด Y เดียวกันและ X อยู่ในช่วงระหว่าง minX และ maxX ให้นับจุดนั้น

ตัวอย่างโค้ด

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

ผลลัพธ์

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