만들 수 있는 좌표 쌍의 수를 찾는 C++ 프로그램

2차원 평면에 2n개의 좌표가 주어졌다고 가정하자. 2n 좌표는 coordA 및 coordB의 두 배열로 나뉩니다. 좌표는 정수 쌍으로 표시됩니다. 이제 coordA의 한 점과 coordB의 한 점을 포함하는 좌표 쌍을 형성해야 합니다. coordA로부터의 점의 x좌표가 coordB로부터의 점의 x좌표보다 작고 coordA로부터의 점의 y좌표가 coordB로부터의 점보다 작은 경우에만 쌍을 만들 수 있습니다. 우리는 우리가 만들 수 있는 쌍의 수를 찾아야 하고, 포인트는 여러 쌍에 속할 수 없습니다.

따라서 입력이 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