The president of Gridland has hired you to design a program that calculates the length of the shortest traveling-salesman tour for the towns in the country. In Gridland, there is one town at each of the points of a rectangular grid. Roads run from every town in the directions North, Northwest, West, Southwest, South, Southeast, East, and Northeast, provided that there is a neighbouring town in that direction. The distance between neighbouring towns in directions North–South or East–West is 1 unit. The length of the roads is measured by the Euclidean distance. For example, Figure 7 shows 2 × 3-Gridland, i.e., a rectangular grid of dimensions 2 by 3. In 2 × 3-Gridland, the shortest tour has length 6.
For each scenario, the grid dimensions m and n will be given as two integer numbers in a single line, separated by a single blank, satisfying 1 < m < 50 and 1 < n < 50.
2 2
2 3
4.00
Scenario #2:
6.00
一道规律题
当n,m有一者能够为偶数时,结果是n*m
否者必有一条路需要斜着走,结果为n*m-1+1.41
#include <stdio.h>
#include <math.h> int main()
{
int t,i = 1;
scanf("%d",&t);
while(t--)
{
double n,m;
scanf("%lf%lf",&n,&m);
printf("Scenario #%d:\n",i++);
if((int)n%2==0 || (int)m%2==0)
printf("%.2lf\n",n*m);
else
printf("%.2lf\n",n*m-1+sqrt(2.0));
printf("\n");
} return 0;
}