별자리 찾기

시간 제한1초메모리 제한128 MB

요약
별자리를 이루는 m개의 점과 사진 속 n개의 별이 주어질 때, 별자리의 모든 점을 사진 속 별로 옮기는 유일한 평행이동을 찾는다.
난이도

쉬움10점 중 3점

유형
해시맵, 완전 탐색
정답자
아직 제출이 없습니다

문제

상근이는 밤하늘 사진에서 특정 별자리를 찾으려고 한다. 사진 속에는 찾고 싶은 별자리와 형태, 방향, 크기가 완전히 같은 도형이 정확히 하나 들어 있다. 다만 사진에는 그 별자리를 이루는 별들 외에 다른 별들도 함께 찍혀 있다.

찾고 싶은 별자리의 모든 별 좌표를 x축 방향으로 dxdx, y축 방향으로 dydy만큼 평행 이동하면 사진 속 별자리의 위치와 정확히 일치한다. (예를 들어 x방향으로 22, y방향으로 −3-3만큼 이동하는 식이다.)

찾고 싶은 별자리의 모양과 사진에 찍힌 모든 별의 위치가 주어질 때, 별자리 좌표를 사진 속 좌표로 옮기기 위한 평행 이동량 (dx,dy)(dx, dy)를 구하는 프로그램을 작성하시오. 이러한 평행 이동은 유일하게 존재한다.

입력

첫째 줄에 찾고 싶은 별자리를 이루는 별의 개수 mm이 주어진다. 이어지는 mm개의 줄에는 별자리를 이루는 각 별의 x좌표와 y좌표가 주어진다.

그 다음 줄에는 사진에 찍힌 별의 개수 nn이 주어지고, 이어지는 nn개의 줄에는 사진 속 각 별의 x좌표와 y좌표가 주어진다.

  • 1≤m≤2001 \le m \le 200
  • 1≤n≤10001 \le n \le 1000
  • 모든 x좌표와 y좌표는 00 이상 1,000,0001{,}000{,}000 이하의 정수이다.

출력

별자리 좌표를 사진 속 좌표로 옮기기 위한 평행 이동량을 한 줄에 출력한다. 첫 번째 정수는 x축 방향 이동량 dxdx, 두 번째 정수는 y축 방향 이동량 dydy이며, 두 정수는 공백으로 구분한다.

예제2

  1. 예제 1

    입력
    5
    8 5
    6 4
    4 3
    7 10
    0 10
    10
    10 5
    2 7
    9 7
    8 10
    10 2
    1 2
    8 1
    6 7
    6 0
    0 9
    
    예상 출력
    2 -3
    
  2. 예제 2

    입력
    5
    904207 809784
    845370 244806
    499091 59863
    638406 182509
    435076 362268
    10
    757559 866424
    114810 239537
    519926 989458
    461089 424480
    674361 448440
    81851 150384
    459107 795405
    299682 6700
    254125 362183
    50795 541942
    
    예상 출력
    -384281 179674