Chessboard

A king wishes to go for a walk of a square chessboard with thefollowing conditions:

• Each two consequent cells of the path must beadjacent, i.e., share an edge or a corner (thus, a cell mayhave up to eight adjacent cells).
• Each cell must be visited exactly once; the first andthe last cells of the path must coincide (thus, the firstcell of the path will be actually visited twice).
• The path must have no self intersections (we may think of apath as a closed polyline with vertices at cells' centers).

Your task is to find the maximal possible length of a king'spath (here we mean the length of the polyline, not thenumber of king's moves).

Input

The first line of the input contains the number of the testcases, which is at most 20.The descriptions of the test cases follow. Eachtest case description consists of an integer N (1 ≤ N ≤ 300), denoting the size of the chessboard. The test casesare separated by blank lines.

Output

For each test case in the input, output a line containingthe length of the king's tour with at least three digitsafter the decimal point. Print a blank line between testcases. The cells have side 1.

Examples

3123

Output

0.0004.0009.414

#include <stdio.h>
#include <math.h>
int main() {
    int testcase, n;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        if(n == 1)
            puts("0.000");
        else if(n == 2)
            puts("4.000");
        else
            printf("%.3lf\n", (n-1)*4 + (n*n-4*(n-1))*sqrt(2));
        if(testcase)
            puts("");
    }
    return 0;
}

題目要求從一點出發，可斜著走，把所有點都走過一次，並且每個點只能走一次，最後回到原點。
問路徑最長為何？

從下圖中，可以發現很明顯的 greedy，盡可能走斜的。