#P18165. Henry the Plumber
Henry the Plumber
Henry the Plumber
Henryk 需要完成若干三维水暖工程。每个工程要把进水口与出水口连接起来,使用若干直管和弯头。弯头把两段管道以直角连接。进水口处必须按给定方向安装第一个弯头,出水口处必须按给定方向安装最后一个弯头。
进水口与出水口的方向都是水平的( 坐标为 0)。
为简化问题,进水口、出水口与所有弯头都是 中的点,管道是零宽度的线段。
进水口与出水口位于不同位置。第一段管道必须从进水口出发,且垂直于进水口方向;之后每段管道必须从上一条管道的末端出发,并与它垂直;最后一段管道必须垂直于出水口方向,并终止于出水口。每段管道长度为正。
管道除在弯头处相接外不能相交:所有弯头必须位于不同点,不能落在任何管道内部,管道之间除公共弯头外不能有公共点。
进水口和出水口处的弯头也计入总数。
对每个工程,判断能否完成;若能,求所需的最少弯头数。
输入格式
第一行一个整数 ()。
每个工程四行:
- 三个整数 (),表示进水口;
- 两个整数 (,),表示进水口方向;
- 三个整数 ,表示出水口;
- 两个整数 ,表示出水口方向。
水沿 方向水平流入(即来自 );沿 方向水平流出(即流向 )。
保证进水口与出水口不同。
输出格式
输出 行,每行一个整数表示最少弯头数,或 NIE 表示无法完成。
样例
输入:
2
-1 -1 3
1 1
2 2 3
2 2
5 5 1
3 0
7 6 -2
1 -2
输出:
4
3
样例解释:第一个工程的最优方案需要四个弯头,例如依次安装在 (-1,-1,3),(-2,0,3),(1,3,3),(2,2,3):

一个较差的六弯头方案是 (-1,-1,3),(-2,0,3),(-1,1,4),(1,-1,4),(3,1,4),(2,2,3):

第二个工程可以在 (5,5,1),(5,5,-2),(7,6,-2) 安装三个弯头:
