弥明来到了新校区。弥明是一个热爱跑步的人,但他不喜欢独自跑步,所以他想找白茶作伴。白茶厌恶跑步,所以让星月陪弥明一同跑步。弥明使用部道乐跑 APP 记录跑步,并定下目标,想要与星月一同完成 30 次部道乐跑任务,每个任务需要跑 2500m ,并且经过两个签到点。由于每次领取任务时,弥明和星月领取到的签到点不都是一样的,而他们又想一起同行。于是,他们决定,从一个起始点出发,按照特定顺序一起依次经过他们加起来的四个签到点。他们想要知道,对于给定的起始点和四个签到点,是否存在一个顺序,使得他们能跑够 2500m(即跑的总距离大于等于 2500m)?如果能,他们还想知道最少需要跑多远?
假设起始点和签到点均分布在平面直角坐标系上,并且都是整点(即横纵坐标均为整数)。假设两点之间的距离均取直线距离。规定输入输出中所有数值的单位为 m。
注:为简单起见,假定他们两个加起来在同一时刻只能选择一个签到点,此时若经过了其他尚未选择的签到点,不算做经过这些签到点。
输入
首先输入一行一个整数 t \ (1\le t\le10^3),代表询问的次数。
对于每个询问,接下来输入 5 行,每行两个整数 x_i,y_i \ (-10^4\le x,y\le10^4),依次代表起始点和四个签到点的坐标。
输出
对于每个询问,若不存在一个顺序使得他们能跑够 2500m,在一行内输出no
;若存在一个顺序使得他们能跑够 2500m,在一行内输出最少需要跑的总路程(四舍五入取整数)。
样例
标准输入 复制文本 |
2 0 0 0 450 0 -450 450 0 -450 0 100 100 400 0 300 0 200 0 100 0 |
标准输出 复制文本 |
2623 no |
提示
对于第一个询问,起始点是 O(0,0),四个签到点分别是 A(0,450),B(0,-450),C(450,0),D(-450,0)。
如果走路线 OABCD,距离是 OA+AB+BC+CD=450+900+450\sqrt{2}+900=2500+2500\sqrt{2}\approx2886;
如果走路线 OACBD,距离是 OA+AC+CB+BD=450+450\sqrt2+450\sqrt2+450\sqrt2=450+1350\sqrt2\approx2359,不够 2500,舍去;
如果走路线 OACDB,距离是 OA+AC+CD+DB=450+450\sqrt2+900+450\sqrt2=1350+900\sqrt2\approx2623;
如果走其他的路线,可以计算发现,其距离均为上面的三个结果之一。
在有效距离 2886,2623 里,2623 最小,故答案为 2623。
对于第二个询问,起始点是 O(100,100),四个签到点分别是 A(400,0),B(300,0),C(200,0),D(100,0),如果选择路线 OBDAC,其距离最长,距离约为 924,最长的距离也小于 2500,所以没有一个距离可以满足,故输出 no
。
注:本询问计算出的所有距离为 400,500,541,600,616,624,641,716,724,741,816,824,841,916,924 。