P7067 [NWRRC 2014] Hiking in the Hills
题目描述
H正在和她的朋友在高原徒步，他们计划着从他们的营地A徒步到一个风景名胜B。
可惜的是，H有了点高原反应。请你帮助他们找到一条路线，使该路线的最高高度尽可能小。
（$1:10^5$）
输入格式
输入数据包含整个$10^6 \times 10^6$的的完整信息，格式如下：
第一行包含了一个整数$n$，表示着这个空间内的三角形的数量。接下来的$n$行，每行包含九个整数，分别是
$x_{i_1},y_{i_1},z_{i_1},x_{i_2},y_{i_2},z_{i_2},x_{i_3},y_{i_3},z_{i_3}$
，是一个三角形的坐标。每个三角形的坐标都在区间[$0, 10^6$]之间。最后两行分别包含了A处的坐标和B处的坐标。
给定的三角形保证在一个一致的坐标系。三角形在XY平面上的投影是非简并的，并且填充正方形而不重叠。一个三角形的顶点永远不会位于另一个三角形的边内。A点和B点属于同一个坐标系，且两者不同位置。
输出格式
输出从A到B的路线，其最高高度可能最小。第一行应包含m，即此多段线中的顶点数。下面的每m条线都应该包含多段线顶点的三个整数坐标。
顶点必须沿路线列出，从A到B（包括这两个端点）。
路线顶点的所有坐标都应为整数。每个多段线边必须属于输入文件（可能是其边）中的某个三角形。路线的拐点数不能超过5n。
说明/提示
Time limit: 2 s, Memory limit: 256 MB.