1695. 弥明爱跑步(25分)

弥明来到了新校区。弥明是一个热爱跑步的人,但他不喜欢独自跑步,所以他想找白茶作伴。白茶厌恶跑步,所以让星月陪弥明一同跑步。弥明使用部道乐跑 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

登录以提交代码。
单点时限 1 秒
内存限制 256 MB
提交 241
通过 88