Stains

Taeyeon has used a rectangular carpet for a long time, so it now carries many permanent stains. She wants to hide them by laying extra carpet patches on top. Each patch is a diamond, an axis-aligned square rotated by $45^\circ$, as shown in Figure 1. The cost of a patch equals its area, and Taeyeon wants to minimize the total cost, that is, the sum of the areas of all patches she uses. She also cares about how it looks, so she lines up the centers of all patches on a single straight line (the x-axis in Figure 1). Patches are allowed to overlap.

Figure 1. The stains are the black dots and the patch centers are the crosses. The thick line is the x-axis.

In this example the nine stains are covered by three patches whose total area is the smallest possible, $32.5 = 18 + 12.5 + 2$.

Every stain has integer coordinates. Find a set of diamond patches such that (1) every stain lies in the interior or on the boundary of at least one patch, (2) the center of every patch lies on the x-axis, and (3) the total area of the patches is as small as possible. All stains are distinct, and no stain lies on the x-axis.

The first line contains the number of test cases $T$. Each test case begins with an integer $n$, the number of stains, where $1 \le n \le 10000$. Each of the next $n$ lines contains two integers: the x-coordinate and the y-coordinate of one stain, each between $-10^6$ and $10^6$ inclusive.

For each test case, print exactly one line with the minimum total area of the patches needed to cover all stains. Print exactly one digit after the decimal point and discard (truncate) any further digits. Because every patch area is a multiple of $0.5$, the printed digit is always $0$ or $5$.