题目描述

Helen is hiking with her friends in a highland. Their plan is to hike from their camp $A$ to a beautiful showplace $B$ .

Unfortunately, Helen started feeling dizzy due to altitude sickness. Help her group find a route such that the topmost height on that route is as small as possible.

输入格式

The input file contains full information about the landscape of a square region $10^{6} \times 10^{6}$ in the following format. The first line contains integer $n$ — the number of triangles in the landscape $(2 \le n \le 2000)$ . Each of following $n$ lines contains nine integers $x_{i_1}, y_{i_1}, z_{i_1}, x_{i_2}, y_{i_2}, z_{i_2}, x_{i3}, y_{i3}, z_{i3}$ — coordinates of a triangle. All coordinates belong to the closed interval $[0 , 10^{6}]$. The two last lines contain three integers each: $x_{A}, y_{A}, z_{A}$ and $x_{B}, y_{B}, z_{B}$ — coordinates of the camp A and the showplace $B$ .

The given triangles are guaranteed to describe a consistent continuous landscape. Projections of triangles onto $XY$ plane are non-degenerate and fill the square without overlapping. A vertex of one triangle never lays inside an edge of another triangle. Points $A$ and $B$ belong to the landscape surface and are different.

输出格式

Output a polyline route from $A$ to $B$ with the smallest possible topmost height. The first line should contain $m$ , the number of vertices in this polyline. Each of following $m$ lines should contain three integer coordinates of a polyline vertex: $x_{i}, y_{i},$ and $z_{i}.$ Vertices must be listed along the polyline, from $A$ to $B$ (including these two endpoints).

All coordinates of polyline vertices should be integer. Each polyline edge must belong to some triangle from the input file (possibly, to its edge). The number of vertices in the polyline must not exceed $5n$.

题目大意

题目描述

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。

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

4
100000 700000 37500
400000 300000 150000
900000 150000 100000
900000 400000 137500

提示

Time limit: 2 s, Memory limit: 256 MB.