문제 소개
삼각형의 세 변에 대한 중점 좌표가 주어졌을 때, 원래 삼각형의 꼭짓점 좌표를 구하는 문제입니다. 예를 들어 중점 좌표가 (5, 3), (4, 4), (5, 5)라고 주어진다면, 우리가 찾아야 할 삼각형의 꼭짓점은 (4, 2), (4, 6), (6, 4)입니다.
해결 접근 방식
이 문제의 핵심은 X좌표와 Y좌표를 서로 분리하여 각각 독립적으로 계산하는 것입니다. 두 축의 계산 과정은 완전히 동일하므로, 한 축에 대한 풀이법만 확립하면 나머지 축에도 그대로 적용할 수 있습니다.
먼저 삼각형 꼭짓점의 X좌표를 각각 x1, x2, x3라고 해 보겠습니다. 그러면 세 변의 중점 X좌표는 다음과 같습니다.
- (x1 + x2) / 2
- (x2 + x3) / 2
- (x3 + x1) / 2
여기서 중요한 성질 하나를 발견할 수 있습니다. 이 세 식을 모두 더하면 분자가 2(x1 + x2 + x3)가 되고, 이를 2로 나누면 결국 x1 + x2 + x3만 남습니다. 즉, 세 중점 X좌표의 합은 곧 세 꼭짓점 X좌표의 합과 같다는 뜻입니다.
이제 우리에게는 '세 변수의 총합'과 '두 변수씩의 합' 세 개, 총 네 가지 정보가 있으므로 간단한 연립방정식 풀이로 각 꼭짓점의 값을 유도할 수 있습니다.
- x1 = (중점 X좌표의 합) − 2 × 두 번째 중점의 X좌표
- x2 = (중점 X좌표의 합) − 2 × 세 번째 중점의 X좌표
- x3 = (중점 X좌표의 합) − 2 × 첫 번째 중점의 X좌표
Y좌표 역시 완전히 동일한 공식을 적용하면 됩니다.
C++ 구현 예제
#include<iostream>
#include<vector>
#define N 3
using namespace std;
vector<int> getResult(int v[]) {
vector<int> res;
int sum = v[0] + v[1] + v[2];
res.push_back(sum - v[1]*2);
res.push_back(sum - v[2]*2);
res.push_back(sum - v[0]*2);
return res;
}
void searchPoints(int mid_x_coord[], int mid_y_coord[]) {
vector<int> x_vals = getResult(mid_x_coord);
vector<int> y_vals = getResult(mid_y_coord);
for (int i = 0; i < 3; i++)
cout << x_vals[i] << " " << y_vals[i] << endl;
}
int main() {
int mid_x_coord[N] = { 5, 4, 5 };
int mid_y_coord[N] = { 3, 4, 5 };
searchPoints(mid_x_coord, mid_y_coord);
}
실행 결과
6 4 4 2 4 6
동작 원리 검증
입력된 중점 X좌표 {5, 4, 5}의 합은 14입니다. 첫 번째 꼭짓점의 X좌표는 14 − 2×4 = 6, 두 번째는 14 − 2×5 = 4, 세 번째는 14 − 2×5 = 4로 계산됩니다. 마찬가지로 중점 Y좌표 {3, 4, 5}의 합은 12이므로 12 − 2×4 = 4, 12 − 2×5 = 2, 12 − 2×3 = 6이 됩니다. 이를 조합하면 (6, 4), (4, 2), (4, 6)이라는 최종 결과를 얻습니다.
복잡도 분석
- 시간 복잡도: O(1) — 고정된 3개의 좌표에 대해 상수 번의 산술 연산만 수행합니다.
- 공간 복잡도: O(1) — 결과를 담는 벡터 외에 추가적인 메모리가 필요하지 않습니다.