Background

15B03 won the right to host ION2064.

Problem Description

The seating in 15B03 is very crowded, and can be seen as an $n\times m$ grid, where each small square $(i, j)$ represents a desk.

According to the rules, no two desks in the exam room may be adjacent. Here, “adjacent” means having a common point. Formally, two desks $(i, j)$ and $(i', j')$ are adjacent if and only if $|i - i'|\leq 1$ and $|j - j'|\leq 1$.

The task of arranging the exam room falls on Little A. He wants to remove as few desks as possible to satisfy the requirement above.

Little A thinks this is too easy, so he adds another constraint: while keeping the number of removed desks minimal, maximize the sum, over all remaining desks, of the distance from each desk to the farthest desk from it. Here, distance means Euclidean distance: the distance between desk $(a, b)$ and $(c, d)$ is $\sqrt{(a - c) ^ 2 + (b - d) ^ 2}$.

In a parallel universe, the size of 15B03 is not always the same: there are multiple test cases.

Please read the scoring rules carefully.

Input Format

The first line contains an integer $S$, indicating the index of this test point.

The second line contains an integer $T$, indicating the number of test cases. Next are $T$ test cases; each test case is:

• One line with two integers $n, m$.

Output Format

For each test case:

• Output an integer and a real number, separated by a space. They represent the minimum number of desks to remove, and the maximum possible value of the sum of “distance from each desk to its farthest desk”.

Real numbers are compared with absolute error or relative error at most $10 ^ {-9}$: let your output be $a$ and the standard answer be $b$. Your answer is accepted if and only if $\frac{|a - b|}{\max(1, |b|)} \leq 10 ^ {-9}$.

0
4
3 3
2 4
15 57
1064 822

5 11.313708499
6 6.324555320
623 10206.135788972
655956 222400384.677931725

Hint

“Sample Explanation”

For the first query, choosing $(1, 1), (1, 3), (3, 1)$, and $(3, 3)$ is optimal. $3\times 3 - 4 = 5$ desks are removed, and for each remaining desk, the distance to its farthest desk is $\sqrt{2 ^ 2 + 2 ^ 2} = 2\sqrt 2$. Therefore, the answer to the second question is $8\sqrt 2$. See the figure below:

For the second query, choosing $(1, 1)$ and $(2, 4)$ is optimal. $2\times 4 - 2 = 6$ desks are removed, and for each remaining desk, the distance to its farthest desk is $\sqrt{1 ^ 2 + 3 ^ 2} = \sqrt {10}$. Therefore, the answer to the second question is $2\sqrt {10}$.

If you choose $(1, 1)$ and $(2, 3)$, then the answer to the second question is $2\sqrt 5$, which is not optimal.

“Scoring Rules”

For each test case:

• If your answer to the first question is wrong, you get 0 points.
• Otherwise, if your answer to the second question is wrong, you get 0.8 points.
• Otherwise, you get 1 point.

The score of each test point is: (the minimum score among all test cases in this test point) multiplied by the score value of this test point.

Note that if your output format is wrong, you get 0 points. Therefore, if you only want the points for the first question, please output any real number within a reasonable range for the second question.

“Constraints and Notes”

• Test point #1 (15 points): both $n, m$ are odd.
• Test point #2 (20 points): $n = 1$.
• Test point #3 (25 points): $n = 2$.
• Test point #4 (30 points): $n$ is odd.
• Test point #5 (10 points): no special restrictions.

For $100\%$ of the data:

• $1\leq T\leq 57$.
• $1\leq n, m\leq 1064$.

“Help and Tips”

• You can use the sqrt(x) function in cmath to compute the square root of $x$. It returns a value of type double. sqrtl(x) has higher precision and returns a value of type long double.

“Source”

• Sweet Round 8 A
• Idea & Solution: Alex_Wei。
• Tester: chenxia25。

Translated by ChatGPT 5