문제 소개
2차원 평면 위에 N개의 점이 입력으로 주어집니다. 목표는 입력된 점들 중 세 점으로 이루어진 삼중항(triplet) 가운데, 한 점이 나머지 두 점을 잇는 선분의 중점(mid-point)이 되는 경우의 수를 구하는 것입니다. 즉, 삼중항이 (A, B, C)일 때 B가 A와 C의 중점이 되어야 하며, 물론 A, B, C 중 어떤 조합이든 상관없습니다.
이 문제는 다음과 같은 방식으로 해결할 수 있습니다. 먼저 모든 점을 pair<int,int> 형태로 벡터(vector)에 저장한 뒤, 벡터의 모든 점을 집합(set)에 추가합니다. 그다음 집합에서 두 점씩 선택하여 두 점의 (x, y) 좌표 합을 2로 나눈 값이 동일한 집합 안에 존재하는지 확인하고, 존재한다면 삼중항 개수를 하나씩 증가시킵니다.
예제를 통해 자세히 살펴보겠습니다.
예제 1
입력
{ 1,2 }, { 4,2 }, { 2,1 }, { 7,2 } — N=4개의 점출력
주어진 조건을 만족하는 삼중항 쌍의 개수: 1
설명
이 경우 {4,2}는 {1,2}와 {7,2} 사이의 중점입니다. 따라서 조건을 만족하는 삼중항은 1개입니다.
예제 2
입력
{ 1,2 }, { 4,2 }, { 2,1 }, { 5,2 }, { 8,1 }, { 1,1 } — N=6개의 점출력
주어진 조건을 만족하는 삼중항 쌍의 개수: 1
설명
이 입력에서는 조건을 만족하는 삼중항이 존재하지 않습니다.
접근 방식
<int,int>타입의 pair를 원소로 갖는 벡터를 사용합니다.- 각 pair는 점의 (x, y) 좌표를 나타냅니다.
- 함수
mid_point(vector<pair<int, int>> vec, int size)는 벡터와 그 크기를 입력받아 중점 조건을 만족하는 삼중항의 개수를 반환합니다. - 삼중항을 세기 위한 변수 count를 초기값 0으로 선언합니다.
- 벡터의 모든 pair를
set<pair<int, int>>에 삽입합니다. 이 집합에는 중복이 제거된 고유한 점들이 저장됩니다. - 두 개의 for 루프를 중첩하여 가능한 모든 점 쌍을 순회합니다.
- 두 점의 x 좌표 합을 정수 point_A에, y 좌표 합을 정수 point_B에 저장합니다.
- point_A와 point_B가 모두 짝수일 때만 중점 조건을 검사합니다. 좌표 합이 홀수면 중점이 정수 좌표가 될 수 없기 때문입니다.
- 집합에 (point_A/2, point_B/2)라는 pair가 존재하면 해당 지점이 중점이라는 의미이므로 count를 증가시킵니다.
- 모든 반복이 끝나면 count에는 조건을 만족하는 삼중항의 총 개수가 저장되며, 이 값을 결과로 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int mid_point(vector<pair<int, int>> vec, int size){
int count = 0;
set<pair<int, int> > sets;
for (int i = 0; i < size; i++){
sets.insert(vec[i]);
}
for (int i = 0; i < size; i++){
for (int j = i + 1; j < size; j++){
int point_A = vec[i].first + vec[j].first;
int point_B = vec[i].second + vec[j].second;
if (point_A % 2 == 0 && point_B % 2 == 0){
if (sets.find(make_pair(point_A / 2, point_B / 2)) != sets.end()){
count++;
}
}
}
}
return count;
}
int main(){
vector<pair<int, int>> vec = { { 9, 2 }, { 5, 2 }, { 1, 2 } };
int size = vec.size();
cout<<"주어진 조건을 만족하는 2차원 공간의 점 삼중항 쌍(A, B, C)의 개수: "<<mid_point(vec, size);
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
주어진 조건을 만족하는 2차원 공간의 점 삼중항 쌍(A, B, C)의 개수: 1
이 예제에서 {9,2}와 {1,2}의 중점은 {5,2}이므로, 조건을 만족하는 삼중항이 정확히 하나 존재함을 확인할 수 있습니다. 이 알고리즘은 시간 복잡도 O(N² log N)으로 동작하며, 집합(set)을 활용해 중점 존재 여부를 효율적으로 판단한다는 점이 핵심입니다.