弥明来到了新校区。弥明是一个热爱跑步的人,但他不喜欢独自跑步,所以他想找白茶作伴。白茶厌恶跑步,所以让星月陪弥明一同跑步。弥明使用部道乐跑 APP 记录跑步,并定下目标,想要与星月一同完成 次部道乐跑任务,每个任务需要跑 ,并且经过两个签到点。由于每次领取任务时,弥明和星月领取到的签到点不都是一样的,而他们又想一起同行。于是,他们决定,从一个起始点出发,按照特定顺序一起依次经过他们加起来的四个签到点。他们想要知道,对于给定的起始点和四个签到点,是否存在一个顺序,使得他们能跑够 (即跑的总距离大于等于 )?如果能,他们还想知道最少需要跑多远?
假设起始点和签到点均分布在平面直角坐标系上,并且都是整点(即横纵坐标均为整数)。假设两点之间的距离均取直线距离。规定输入输出中所有数值的单位为 。
注:为简单起见,假定他们两个加起来在同一时刻只能选择一个签到点,此时若经过了其他尚未选择的签到点,不算做经过这些签到点。
输入
首先输入一行一个整数 ,代表询问的次数。
对于每个询问,接下来输入 行,每行两个整数 ,依次代表起始点和四个签到点的坐标。
输出
对于每个询问,若不存在一个顺序使得他们能跑够 ,在一行内输出no
;若存在一个顺序使得他们能跑够 ,在一行内输出最少需要跑的总路程(四舍五入取整数)。
样例
标准输入 复制文本 |
2 0 0 0 450 0 -450 450 0 -450 0 100 100 400 0 300 0 200 0 100 0 |
标准输出 复制文本 |
2623 no |
提示
对于第一个询问,起始点是 ,四个签到点分别是 。
如果走路线 ,距离是 ;
如果走路线 ,距离是 ,不够 ,舍去;
如果走路线 ,距离是 ;
如果走其他的路线,可以计算发现,其距离均为上面的三个结果之一。
在有效距离 里, 最小,故答案为 。
对于第二个询问,起始点是 ,四个签到点分别是 ,如果选择路线 ,其距离最长,距离约为 ,最长的距离也小于 ,所以没有一个距离可以满足,故输出 no
。
注:本询问计算出的所有距离为 。