겹쳐 놓은 지도

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

요약
큰 지도 위에 놓인 축소되고 회전한 작은 지도에서 두 지도 모두 같은 장소를 가리키는 유일한 점을 찾는다.
난이도

보통10점 중 4점

유형
기하, 수학, 구현, 이분 탐색
정답자
아직 제출이 없습니다

문제

Fred와 Sam이 함께 여행을 하고 있다. 두 사람 모두 같은 지역의 지도를 가지고 있다. 두 지도는 완전히 똑같은 영역을 담고 있고 가로세로 비율도 정확히 같지만, Sam의 지도는 Fred의 지도보다 축척이 작아서 크기가 조금 더 작다.

Fred가 자신의 지도를 탁자 위에 펼쳐 놓는다. Sam이 자신의 지도를 그 위에 던져 올린다. 작은 지도는 위치가 어긋나고 회전된 채로 놓이지만, 여전히 큰 지도 위에 완전히 포개진다. Fred가 작은 지도에 핀을 꽂자 핀이 큰 지도까지 관통한다. Sam은 놀라며 말한다. “우와! 저 핀이 가리키는 위치가 두 지도에서 똑같은 장소를 나타내!” Fred가 답한다. “그리 놀라운 일은 아니야. 그런 점은 항상 정확히 하나 존재하거든.”

큰 지도의 크기와, 그 위에 완전히 포개진 작은 지도의 위치(offset), 축척, 회전이 주어질 때, 두 지도에서 똑같은 장소를 가리키는 유일한 점을 구하여라.

입력

입력에는 여러 개의 테스트 케이스가 주어진다. 각 테스트 케이스는 여섯 개의 정수로 이루어진 한 줄이다.

w h x y s r
  • ww와 hh (0<w,h≤10000 < w, h \le 1000)는 큰 지도의 너비와 높이다. 큰 지도는 평면 위에 놓이며, 남서쪽 모서리는 원점, 북서쪽 모서리는 (0,h)(0, h), 남동쪽 모서리는 (w,0)(w, 0), 북동쪽 모서리는 (w,h)(w, h)에 있다.
  • xx와 yy (0≤x≤w0 \le x \le w, 0≤y≤h0 \le y \le h)는 작은 지도의 남서쪽 모서리가 놓인 평면 좌표다.
  • ss (0<s<1000 < s < 100)는 큰 지도에 대한 작은 지도의 축척을 백분율로 나타낸 값이다 (s=50s = 50이면 작은 지도의 너비와 높이가 큰 지도의 절반임을 뜻한다).
  • rr (0≤r<3600 \le r < 360)은 작은 지도를 자신의 남서쪽 모서리를 중심으로 반시계 방향으로 회전시킨 각도(도 단위)다 (r=90r = 90이면 남동쪽 모서리가 남서쪽 모서리의 정북 방향으로 회전한다).

작은 지도는 항상 큰 지도의 경계 안에 완전히 들어오도록 주어진다. 입력의 마지막 줄은 여섯 개의 0으로 이루어지며, 이 줄은 처리하지 않는다.

출력

각 테스트 케이스마다 두 지도에서 똑같은 장소를 가리키는 점의 좌표 xx와 yy를 실수 두 개로 출력한다. 각 수는 소수점 아래 정확히 두 자리로 반올림하여, 사이에 공백 하나를 두고 출력한다. 여분의 공백을 출력하지 말고, 테스트 케이스 사이에 빈 줄을 넣지 마라.

예제3

  1. 예제 1

    입력
    100 100 50 50 25 0
    100 100 50 50 25 45
    0 0 0 0 0 0
    
    예상 출력
    66.67 66.67
    45.59 70.53
    
  2. 예제 2

    입력
    200 100 20 10 40 0
    0 0 0 0 0 0
    
    예상 출력
    33.33 16.67
    
  3. 예제 3

    입력
    100 100 60 20 30 90
    0 0 0 0 0 0
    
    예상 출력
    49.54 34.86