빅 서프라이즈
시간 제한2초메모리 제한512 MB
축에 평행한 직육면체 건물 최대 100개가 주어질 때, 건물을 피해 두 점을 잇는 최단 직각 경로 길이를 구합니다.
문제
TetrisCity의 젊은 시장이 소셜 미디어에 "다음 주 목요일에 큰 놀라움이 찾아온다!"라고 발표했다. TetrisCity는 Neverland에서 인구가 가장 많고 현대적인 도시다. 평평한 땅 위에 고층 건물이 테트리스 게임처럼 촘촘히 모여 있다. 각 건물은 땅 위에 세워진 축에 평행한 직육면체이며, 건물끼리는 서로 겹치지도 않고 닿지도 않는다.
이 큰 놀라움은 드론을 이용한 특별 배송 서비스다. 드론은 x, y, z 방향 중 한 방향으로만 움직일 수 있는 쿼드콥터다. 따라서 드론이 이동한 거리는 각 축 방향으로 이동한 거리의 합이다. 시장은 건물을 피해 임의의 출발점에서 임의의 도착점까지의 최단 경로를 계산하는 소프트웨어를 주문했다. 여러분의 일은 이 소프트웨어를 개발하는 것이다.
입력
첫 줄에 건물의 개수 n(0 ⩽ n ⩽ 100)이 주어진다. 이어지는 n개의 줄에는 공백으로 구분된 정수 5개 x, y, x′, y′, h가 주어진다. (x, y)는 건물의 남서쪽 모서리, (x′, y′)는 북동쪽 모서리이고, h는 건물의 높이다. 모든 건물의 부피는 0이 아니다.
출발점과 도착점은 입력의 끝에 각각 별도의 줄에 주어진다. 각 줄에는 x, y, z 좌표가 들어 있다. 입력의 모든 수는 100 000 이하의 음이 아닌 정수다. 출발점과 도착점은 건물 바깥에 있으며, 건물의 경계 위에 있을 수도 있다. 최단 경로는 건물에 닿을 수 있고, 드론은 점으로 취급한다.
출력
건물을 피해 출발점에서 도착점까지 이동하는 최단 경로의 길이를 출력한다.