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

2次元平面上に2n個の座標が与えられているとします。 2n座標は、coordAとcoordBの2つの配列に分割されます。座標は整数のペアとして表されます。次に、coordAからの1つのポイントとcoordBからの1つのポイントを含む座標ペアを形成する必要があります。 coordAからの点のx座標がcoordBからの点のそれよりも小さく、coordAからの点のy座標がcoordBからの点のy座標よりも小さい場合にのみ、ペアを作成できます。作ることができるペアの数を見つける必要があり、ポイントは複数のペアに属することはできません。

したがって、入力がn =3のようである場合、coordsA ={{1、3}、{2、4}、{4、3}}、coordsB ={{2、2}、{4、2}、{0 、2}}の場合、出力は1になります。

作成できるペアは（1、3）と（0、2）のみです。

これを解決するには、次の手順に従います-

Define an array chk of size: 100 initialized with 0
sort the array coordA
sort the array coordB
k := 0
for initialize i := n - 1, when i >= 0, update (decrease i by 1), do:
for initialize j := 0, when j < n, update (increase j by 1), do:
if chk[j] is same as 0 and first value of coordA[i] < second value of coordB[j] and second value of coordA[i] < first value of coordB[j], then:
chk[j] := 1
(increase k by 1)
Come out from the loop
print(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