고지대 산행

시간 제한2초메모리 제한256 MB

요약

삼각형으로 이루어진 지형을 지나 야영지 A에서 전망대 B까지 이동할 때 가장 높은 지점의 높이가 가장 낮아지는 경로의 높이를 구합니다.

난이도: 보통10점 중 7점
유형: 유니온 파인드, 최소 신장 트리, 기하, 그래프
정답자: 아직 제출이 없습니다

문제

헬렌은 친구들과 고지대를 걷고 있다. 야영지 A에서 전망대 B까지 걸어가는 것이 이번 일정이다.

헬렌이 고산병으로 어지러움을 느끼기 시작했다. 지나는 지점의 고도 중 가장 높은 값이 최대한 낮은 경로를 찾아 주자.

지형은 삼각형 여러 개로 주어진다. 경로는 A에서 B까지 이어지는 꺾은선이고, 경로를 이루는 각 선분은 삼각형 하나에 완전히 들어가야 한다. 즉 경로는 지형 표면을 벗어나지 않는다. 경로의 최고 고도는 그 경로 위에 있는 점의 $z$ 좌표 중 가장 큰 값이다. A에서 B까지 가는 모든 경로 가운데 최고 고도의 최솟값을 구하라.

입력

지형은 $10^6 \times 10^6$ 크기의 정사각형 영역을 덮는다.

첫 줄에 지형을 이루는 삼각형의 개수 $n$ 이 주어진다 ( $2 \le n \le 2000$ ).

다음 $n$ 개의 줄에는 삼각형 하나의 좌표를 나타내는 정수 아홉 개 $x_{i1}$ , $y_{i1}$ , $z_{i1}$ , $x_{i2}$ , $y_{i2}$ , $z_{i2}$ , $x_{i3}$ , $y_{i3}$ , $z_{i3}$ 이 주어진다. 모든 좌표는 닫힌구간 $[0, 10^6]$ 에 속한다.

마지막 두 줄에는 각각 정수 세 개가 주어진다. 야영지 A의 좌표 $x_A$ , $y_A$ , $z_A$ 와 전망대 B의 좌표 $x_B$ , $y_B$ , $z_B$ 이다.

주어진 삼각형은 끊긴 곳 없이 이어진 지형 하나를 이룬다. 삼각형을 XY 평면에 정사영한 도형은 모두 넓이가 0이 아니며, 서로 겹치지 않으면서 정사각형을 빈틈없이 채운다. 한 삼각형의 꼭짓점이 다른 삼각형의 변 내부에 놓이는 일은 없다. A와 B는 지형 표면 위에 있는 서로 다른 점이다.

출력

A에서 B까지 가는 경로의 최고 고도가 가질 수 있는 가장 작은 값을 정수 하나로 출력한다.

예제3

예제 1

입력

8
1000000 0 0 1000000 1000000 150000 600000 600000 400000
0 1000000 0 600000 600000 400000 600000 1000000 300000
0 1000000 0 400000 300000 150000 600000 600000 400000
400000 0 200000 1000000 0 0 400000 300000 150000
400000 300000 150000 1000000 0 0 600000 600000 400000
600000 600000 400000 1000000 1000000 150000 600000 1000000 300000
0 0 0 400000 0 200000 400000 300000 150000
0 1000000 0 0 0 0 400000 300000 150000
100000 700000 37500
900000 400000 137500

예상 출력

예제 2

입력

2
0 0 800 1000000 0 0 1000000 1000000 900
0 0 800 1000000 1000000 900 0 1000000 0
900000 100000 170
100000 900000 170

예상 출력

예제 3

입력

8
0 0 0 500000 0 900 500000 500000 300
0 0 0 500000 500000 300 0 500000 0
0 500000 0 500000 500000 300 500000 1000000 900
0 500000 0 500000 1000000 900 0 1000000 0
500000 0 900 1000000 0 0 1000000 500000 0
500000 0 900 1000000 500000 0 500000 500000 300
500000 500000 300 1000000 500000 0 1000000 1000000 0
500000 500000 300 1000000 1000000 0 500000 1000000 900
0 0 0
1000000 1000000 0

예상 출력