#P9830. [ICPC 2020 Shanghai R] Traveling in the Grid World
[ICPC 2020 Shanghai R] Traveling in the Grid World
题目描述
Consider a grid pattern with rows and columns. There are 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 ().
There are some constraints when you travel in the grid world. When you are located at point , you can choose a destination and walk to it along the line segment between and . We call this operation a . 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 to and then walk from to , you must make sure that .) The length of a walk from to is defined as the Euclidean distance between the two endpoints, .
Starting from , you are planning to arrive at 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 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 of over 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 .
2
2 2
2 3
3.236067977499790
3.605551275463989