#P9830. [ICPC 2020 Shanghai R] Traveling in the Grid World

    ID: 11072 远端评测题 1000ms 1024MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>数学贪心2020上海Special JudgeO2优化ICPC

[ICPC 2020 Shanghai R] Traveling in the Grid World

题目描述

Consider a grid pattern with nn rows and mm columns. There are (n+1)×(m+1)(n+1)\times(m+1) grid points in total which is the intersections of n+1n+1 horizontal lines and m+1m+1 vertical lines. We number the horizontal lines from 00 to nn from top to bottom. We number the vertical lines from 00 to mm from left to right. The intersection of horizontal line ii and vertical line jj is named (i,j)(i, j) (0in,0jm0\le i\le n, 0\le j\le m).

There are some constraints when you travel in the grid world. When you are located at point (x,y)(x,y), you can choose a destination (x,y)(x',y') and walk to it along the line segment between (x,y)(x, y) and (x,y)(x', y'). We call this operation a walk\textit{walk}. A walk is forbidden if there exists another grid point different from (x,y)(x, y) and (x,y)(x', y') 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 (x0,y0)(x_0, y_0) to (x1,y1)(x_1, y_1) and then walk from (x1,y1)(x_1, y_1) to (x2,y2)(x_2, y_2), you must make sure that (x0x1)(y1y2)(x1x2)(y0y1)(x_0-x_1)(y_1-y_2)\neq (x_1-x_2)(y_0-y_1).) The length of a walk from (x,y)(x, y) to (x,y)(x', y') is defined as the Euclidean distance between the two endpoints, (xx)2+(yy)2\sqrt{(x-x')^2+(y'-y)^2}.

Starting from (0,0)(0,0), you are planning to arrive at (n,m)(n,m) 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 TT, indicating the number of test cases. For each test case:

The first line contains two integers n,mn,m (1n,m1061\le n,m \le 10^6) indicating the size of the grid graph.

It is guaranteed that the sum of the values of max(n,m)\max(n,m) over all test cases does not exceed 10610^6.

输出格式

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 10910 ^{-9}.

2
2 2
2 3
3.236067977499790
3.605551275463989