时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
Special Judge, 64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
Special Judge, 64bit IO Format: %lld
题目描述
Consider a grid pattern with 
rows and 
columns. There are %5Ctimes(m%2B1))
grid points in total which is the intersections of 
horizontal lines and 
vertical lines. We number the horizontal lines from 
to from top to bottom. We number the vertical lines from to from left to right. The intersection of horizontal line 
and vertical line 
is named %7D)
)
.
There are some constraints when you travel in the grid world. When you are located at point%7D)
, you can choose a destination %7D)
and walk to it along the line segment between %7D)
and %7D)
. We call this operation a walk. A walk is forbidden if there exists another grid point different from and lying on the line segment between them. You can walk as many times as you want but the directions of two consecutive walks cannot be the same. (Specifically, if you walk from %7D)
to %7D)
and then walk from to %7D)
, you must make sure that (y_1-y_2)%5Cneq%20(x_1-x_2)(y_0-y_1))
.) The length of a walk from to is defined as the Euclidean distance between the two endpoints, %5E2%2B(y'-y)%5E2%7D)
.
Starting from%7D)
,you are planning to arrive at %7D)
by several walks. Because of the annoying rules, you may need some turning points to achieve your goal. Please find the minimum total length of your walks.
There are some constraints when you travel in the grid world. When you are located at point
Starting from
输入描述:
There are multiple test cases. The first line of the input contains an integer, indicating the number of test cases. For each test case:
The first line contains two integers(
) indicating the size of the grid graph.
It is guaranteed that the sum of the values ofover all test cases does not exceed
.
输出描述:
For each test case, output the minimum total length of walks. Your answer will be considered correct if its absolute or relative error does not exceed.