에테르 기하학

알렉산드리아에 살던 에우클레이데스는 유클리드 기하학에는 왕도가 없다고 굳게 믿고 있었다. 그러던 그는 신문 기사를 읽고 TV 프로그램을 보며, 젊은 학생들의 말을 듣다 보니 인터넷에서 eGeometry나 Geometry 같은 학문을 만들 수 있을지도 모른다는 생각이 점점 들었다. e-기하 환경에서는 피타고라스 같은 많은 친구와 기하 문제를 제때 토론할 수 있고, 자신의 유명한 자료집 "기하학 원론(Stoicheia)"의 새 판을 웹사이트에 올릴 수도 있다. 그는 곧바로 인터넷에 가입하기로 마음먹었다.

그는 독특한 모양으로 지은 서재에서 허브에서 단말기까지 에테르 케이블을 직접 깔기 시작했다. 그는 케이블 경로가 가능한 한 짧도록 설계했다.

그림 1은 그의 서재 평면도이다. (0 0)처럼 괄호 안의 정수는 가장 가까운 기둥, 허브, 또는 단말기의 x, y 좌표이다. 인접한 두 기둥은 실선으로 그린 벽으로 이어진다. 허브의 위치를 A, 단말기의 위치를 B라고 하면, 가장 짧은 케이블은 그림의 점선처럼 놓인다. 과제는 평면도마다 A와 B 두 끝점을 포함한 최단 케이블 경로의 꺾임점 좌표를 순서대로 출력하는 것이다. 예를 들어 그림 1의 답은 (1 1) (2 2) (8 4) (9 5)이다.

그림 1

다만 이곳은 유클리드 기하학의 창시자이자 대가인 유클리드의 집이다. 기둥, 허브, 단말기는 유클리드 기하학의 이상적인 점이고, 벽과 케이블은 기하학적 의미의 선분이다. 따라서 케이블은 벽이나 기둥과 겹칠 수 있다. 그림 2, 3, 4의 답은 다음과 같다. 이후 서재의 배치는 기둥 좌표 목록으로 제시한다.

그림 2. 기둥: (0 0) (2 0) (2 2) (4 2) (4 0) (6 0) (6 6) (4 6) (4 4) (2 4) (2 6) (0 6). 허브: (1 1). 단말기: (5 1). 답: (1 1) (2 2) (4 2) (5 1)

그림 3. 기둥: (0 0) (2 0) (2 2) (4 2) (4 0) (6 0) (6 6) (4 6) (4 4) (2 4) (2 6) (0 6). 허브: (1 1). 단말기: (5 5). 답: (1 1) (5 5). 주의: (2 2) (4 4)는 꺾임점이 아니다.

그림 4. 기둥: (0 0) (2 0) (2 2) (4 2) (4 0) (6 0) (6 2) (8 2) (8 0) (10 0) (10 6) (8 6) (8 4) (6 4) (6 6) (4 6) (4 4) (2 4) (2 6) (0 6). 허브: (1 1). 단말기: (9 1). 답: (1 1) (2 2) (8 2) (9 1)

그림 2	그림 3	그림 4

그림 5처럼 복잡한 모양의 서재도 풀 수 있는 프로그램을 제출하라. 이 배치는 샘플 입력에 들어 있다.

기둥: (0 0) (2 0) (2 4) (4 4) (4 0) (14 0) (14 6) (10 6) (10 8) (14 8) (14 14) (4 14) (4 10) (2 10) (2 14) (0 14) (0 8) (6 8) (6 12) (12 12) (12 10) (8 10) (8 4) (12 4) (12 2) (6 2) (6 6) (0 6). 허브: (1 1). 단말기: (1 13). 답: (1 1) (2 4) (4 4) (6 2) (12 2) (12 4) (10 6) (10 8) (12 10) (12 12) (6 12) (4 10) (2 10) (1 13)

그림 5

모든 좌표는 정수이다. 벽은 x축이나 y축에 평행하다. 좌표가 주어진 기둥마다 벽이 오른쪽 또는 왼쪽으로 꺾인다. 기둥 좌표는 서재 안쪽을 바라보았을 때 왼쪽으로 도는 순서로 주어진다. 목록의 마지막 기둥 다음 벽은 첫 번째 기둥까지 뻗는다. 같은 위치의 기둥은 목록에 한 번만 나온다. 각 기둥에는 x축에 평행한 벽과 y축에 평행한 벽이 정확히 하나씩 연결된다. 벽 전체는 한 번에 그린 닫힌 선으로 서재를 둘러싼다. 벽끼리 교차하지 않으며, 가지처럼 갈라지는 벽도 없다. 서재 안에는 독립된 벽이나 다른 장애물이 없다. 각 평면도에는 허브와 단말기가 서재 안에 하나씩만 있으며, 두 위치는 항상 다르다.

입력에는 하나 이상의 데이터 세트가 들어 있다. 각 데이터 세트는 기둥 수 n(4 <= n <= 208)을 나타내는 정수 한 줄로 시작한다. 이어지는 줄에는 기둥 좌표가 한 줄에 다섯 쌍씩 주어진다. 그다음 줄에는 허브 좌표 (ax ay)와 단말기 좌표 (bx by)가 주어진다.

n
x1   y1   x2   y2   ...  x5   y5
x6   y6   x7   y7   ...  x10  y10
x11  y11  ...
     ...  xn   yn
ax   ay   bx   by

입출력 값에는 괄호를 쓰지 않는다.

기둥의 좌표는 모두 짝수 정수이고, 허브와 단말기의 좌표는 모두 홀수 정수이다. 방의 크기는 x, y 방향 모두 100 미만이며, 케이블의 길이는 1000 미만이다.

입력은 마지막 데이터 세트 뒤에 0만 한 줄로 적힌 줄이 나오면 끝난다.

각 데이터 세트마다 최단 케이블의 꺾임점 좌표를 출력한다. 출력은 허브 좌표로 시작하고 단말기 좌표로 끝난다. 한 줄에는 좌표 쌍을 다섯 개씩 한 칸 띄어 출력한다. 마지막 줄은 다섯 개보다 적을 수 있다. 각 쌍의 x와 y 값도 한 칸 띄어 구분한다. 줄의 마지막 좌표 뒤에 한 칸의 공백이 붙어도 된다. 각 데이터 세트의 답 뒤에는 빈 줄을 하나 출력한다.