Traveling in the Grid World

题意：
从(0,0)走到(n,m)，选择一个中转点(x1,y1)，然后从(x0,y0)沿直线走到中转点且中间不经过任何一个点称为一次散步，输出所有散步的最小总长度。

思路：
要记的结论：一对不互质的数(n,m)一定可以被分解为两对互质的数(i,j)和(n-i,m-j)之和( (i,j)与就在(0,0)和(n,m)的直线附近 )。(因为不会证)

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+7,maxm=2e5+7,mod=999911659;
typedef long long int ll;
#define eb emplace_back
#define ef emplace_front
#define ep emplace
#define fi first
#define se second
inline double dis(int n,int m){
    return sqrt(1.0*n*n+1.0*m*m);
}
inline void solve() {
    int n,m;
    double ans=1e18;
    scanf("%d%d",&n,&m);
    if(__gcd(n,m)==1) {
        printf("%.15f\n",dis(n,m));
        return;
    }
    for(int i=1,j;i<=n;++i) {
        j=(m*i-1)/n;
        ans=min(ans,dis(i,j)+dis(n-i,m-j));
    }
    printf("%.15f\n",ans);
}
int main() {
    int t;
    scanf("%d",&t);
    while(t--) solve();
    return 0;
}