BOJ 1894 - 4번째 점

문제

BOJ 1894 - 4번째 점

직사각형의 세 꼭짓점 좌표가 주어질 때 나머지 한 꼭짓점의 좌표를 구하는 문제이다. 입력은 두 쌍의 점(p1-p2, p3-p4)으로 주어지며, 각 쌍이 반드시 대각선 관계는 아니다. EOF까지 반복 처리한다.

입력

각 줄에 8개의 실수(p1.x p1.y p2.x p2.y p3.x p3.y p4.x p4.y)가 주어진다.

출력

각 줄마다 4번째 꼭짓점 좌표를 소수점 셋째 자리까지 출력한다.

예제

풀이

두 쌍의 점에서 공유점을 찾아 쌍을 재정렬한 뒤, 벡터 합으로 4번째 꼭짓점을 계산하는 기하학 구현 문제이다.

1. 입력된 두 쌍 (p1, p2), (p3, p4)에서 같은 점이 있으면 대각선-변 관계를 바로잡는다.
   • p2 == p3이면 p1과 p2를 swap하여 p1이 공유점이 되게 한다.
   • p1 == p4이면 p3과 p4를 swap한다.
   • p2 == p4이면 p1-p2 swap 후 p3-p4 swap을 모두 수행한다.
2. 정렬 후 p1이 공유점, p2와 p4가 각각 인접 꼭짓점이 된다.
3. 4번째 점 = p1 + (p2 - p1) + (p4 - p1) = p2 + p4 - p1으로 계산한다.

핵심 아이디어: 직사각형에서 한 꼭짓점과 두 인접 꼭짓점이 알려지면 4번째 꼭짓점은 벡터 합으로 바로 구할 수 있다. 공유점을 기준으로 쌍을 정렬하는 것이 핵심이다.

코드

#include <iostream>
#include <vector>
#include <utility>
using namespace std;
typedef long double ld;
 
pair<ld, ld> p1, p2, p3, p4;
 
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
 
  cout << fixed;
  cout.precision(3);
 
  while (cin >> p1.first >> p1.second >> p2.first >> p2.second >> p3.first >> p3.second >> p4.first >> p4.second)
  {
    if (p2 == p3)
      swap(p1, p2);
    else if (p1 == p4)
      swap(p3, p4);
    else if (p2 == p4)
      swap(p1, p2), swap(p3, p4);
    cout << p1.first + (p2.first - p1.first) + (p4.first - p1.first) << ' ' << p1.second + (p2.second - p1.second) + (p4.second - p1.second) << '\n';
  }
}

복잡도

• 시간: O(T) (T: 입력 케이스 수, 케이스당 O(1))
• 공간: O(1)