C++で作成できる座標ペアの数を求めるプログラム

問題概要

2次元平面上に与えられた2n個の座標点を考えます。これらの座標は、coordAとcoordBという2つの配列に分けられており、各座標は整数のペアで表されます。ここで、coordAから1点、coordBから1点を選んでペアを作ることを考えます。ペアを作成できるのは、coordA側の点のx座標がcoordB側の点のx座標より小さく、かつcoordA側の点のy座標がcoordB側の点のy座標より小さい場合のみです。さらに、1つの点が複数のペアに属することはできないものとします。このとき、作成できるペアの総数を求めます。

例として、入力が n = 3、coordsA = {{1, 3}, {2, 4}, {4, 3}}、coordsB = {{2, 2}, {4, 2}, {0, 2}} の場合、出力は 1 になります。このとき作成できる唯一のペアは、(1, 3) と (0, 2) の組み合わせです。

アルゴリズム

この問題を解くために、以下の手順に従います。

• サイズ100の配列chkを宣言し、すべて0で初期化します(各点の使用済みを示すフラグです)。
• 配列coordAをソートします。
• 配列coordBをソートします。
• ペア数を数える変数kを0で初期化します。
• i を n-1 から 0 まで減らしながらループします。
  j を 0 から n-1 まで増やしながらループします。
  chk[j] が 0 であり、かつ座標の大小条件を満たす場合は、chk[j] を 1 に設定し、k を1増やして内側のループを抜けます。
• 最後に k を出力します。

実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
#define N 100
void solve(int n, vector<pair<int,int>> coordA, vector<pair<int,int>>coordB){
    int i, j, k;
    int chk[100] = {0};
    sort(coordA.begin(),coordA.end());
    sort(coordB.begin(),coordB.end());
    k = 0;
    for(i = n - 1; i >= 0; i--) {
        for(j = 0; j < n; j++) {
            if(chk[j] == 0 && coordA[i].first < coordB[j].second && coordA[i].second < coordB[j].first) {
                chk[j] = 1;
                k++;
                break;
            }
        }
    }
    cout<< k;
}
int main() {
    int n = 3;
    vector<pair<int,int>> coordsA = {{1, 3}, {2, 4}, {4, 3}};
    vector<pair<int,int>> coordsB = {{2, 2}, {4, 2}, {0, 2}};
    solve(n, coordsA, coordsB);
    return 0;
}

入力

3, {{1, 3}, {2, 4}, {4, 3}}, {{2, 2}, {4, 2}, {0, 2}}

出力

1