C++で上下左右のいずれかに少なくとも1つの点が存在する点の個数を求める方法

この問題では、2次元平面上に配置されたN個の点が与えられます。目的は、自分の「上」「下」「左」「右」のいずれかに少なくとも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

この例では、点{1, 1}に対して上に{1, 2}、下に{1, 0}、左に{0, 1}、右に{2, 1}が存在しているため、条件を満たす点は{1, 1}のみとなり、出力は1になります。

解法アプローチ

この問題を効率的に解くには、各点ごとに「隣接し得る点の座標範囲（最小値・最大値）」を事前に求めておく手法が有効です。手順は以下の通りです。

1. 各点の座標にオフセット（OFF = 1000）を加算し、負の座標でも配列のインデックスとして扱えるようにします。
2. 同じY座標を持つ点群の中でのX座標の最小値・最大値を、それぞれ配列minX・maxXに記録します。
3. 同様に、同じX座標を持つ点群の中でのY座標の最小値・最大値を、配列minY・maxYに記録します。
4. 各点について、そのX座標が同じY座標の点群における最小値と最大値の間にあり、かつそのY座標も同じX座標の点群における最小値と最大値の間にある場合、条件を満たすものとしてカウントを1増やします。

最終的なカウント値を変数に保持し、結果として返します。

C++による実装例

#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

計算量の目安

• 時間計算量：O(N + MX)（点の数Nに対してほぼ線形時間で処理可能）
• 空間計算量：O(MX)（座標の取りうる範囲MXに依存した追加メモリが必要）