T. 教堂(思维数论)

T. 教堂
Description
ROMA城中有一些古典的印度式建筑，这些建筑和周围的欧洲建筑风格格格不入。这些伪装成教堂的建筑其实是某国特工的基地。Tomas接受了一项任务，就是从某个教堂出发，逐个访问这些教堂，搞清楚每一个教堂的内部结构，并回到出发的地方。这些教堂很有规律地构成了一个m∗n的矩形，每个教堂和它的八个方向的教堂有直接的路径相连。水平或垂直方向相邻的教堂之间的路程均为1。请问Tomas至少需要走多远的路，才能完成这个危险而艰巨的任务呢？

Input
输入一行两个整数m和n（m,n≤10000）

Output
输出一行一个实数，表示最少需要走的路程，保留两位小数。

Samples
Input 复制
2 3
Output
6.00
题意： 给你一个n*m的矩形，让你走完所有格并且最后回到原地。问最小步数？
思路： 我们首相考虑边界信息，当只有一行或一列时：那么图形就是这样的

就像这样的，只是简图。我们可以从头走到最后让后从最后回来就是(max(n,m)-1)*2.
然后我们看具体的。当n和m以一个是偶数时我们就可以用蛇形走位直接走回起点，就是把所有的直接走完，不走多余路。

剩下的其实就是两个都是奇数，那么我们其实就是多走了一个斜边。

其实就是(m*n-1)+1.414.

代码放着了。

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include <immintrin.h>
#pragma GCC optimize(2)
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pii;
#define PI acos(-1)
const int maxn=2e5+7;
#define x first
#define y second
#define inf 0x3f3f3f3f
#define lowbit(x)  ((x) & - (x))
const int mod=998244353;
const int dx[]= {0,1,0,-1};//下 上 右 左
const int dy[]= {1,0,-1,0};
int day[]= {0,31,28,31,30,31,30,31,31,30,31,30,31};
const int MOD=100003;
inline ll read() {char c=getchar();ll f=1,x=0;while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();return x*f;
}
void out(ll a) { //代替printf，速度更快，俗称输出挂if(a > 9) {out(a/10);}putchar(a%10 + '0');
}
ll a[1010][1010];
ll tree1[1010][1010];void update1(ll num,ll x,ll d) {while(x<=1000) {tree1[num][x]+=d;x+=lowbit(x);}
}ll   sum1(ll num,ll x) {ll ans = 0;while(x>0) {ans+=tree1[num][x];x-=lowbit(x);}return ans;
}
int main(){ll n,m;cin>>n>>m;if(n==1||m==1){printf("%.2lf",double(m+n-2)*2);}else {if(m*n%2==0){printf("%.2lf\n",double(n*m));}else printf("%.2lf\n",double(m*n+0.414));        }return 0;
}