F. Fairly Easy Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

One of the problems in your "Advanced Geometry, Algebra, and Programming" book is as follows. You are given $$$n$$$ points $$$C_1, C_2, \ldots, C_n$$$ on a plane ($$$C_i \ne C_{i + 1}$$$ for any $$$i$$$). There is also another point $$$D$$$, which is different from all points $$$C_i$$$. You are to draw $$$n$$$ circles $$$\omega_1, \omega_2, \ldots, \omega_n$$$, and also $$$n - 1$$$ tangents $$$l_1, l_2, \ldots, l_{n - 1}$$$ to them, ensuring that all of the following conditions are satisfied:

  • for all $$$i$$$ from $$$1$$$ to $$$n$$$, the center of circle $$$\omega_i$$$ is point $$$C_i$$$;
  • for all $$$i$$$ from $$$1$$$ to $$$n - 1$$$, line $$$l_i$$$ passes through point $$$D$$$ and is tangent to both circles $$$\omega_i$$$ and $$$\omega_{i + 1}$$$;
  • for all $$$i$$$ from $$$1$$$ to $$$n - 2$$$, if circle $$$\omega_{i + 1}$$$ does not pass through $$$D$$$, then lines $$$l_i$$$ and $$$l_{i + 1}$$$ do not coincide;
  • the total area of all circles should be maximized. (Note that this is not the same as the area of the circles' union.)

Sadly, none of your friends can help you, as they can solve the problem only if the last of the four conditions is absent, in which case the problem becomes fairly easy. Since the book also covers Programming, it does not provide all the input points on paper, so you have to generate some of them yourself...

Input

The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 3 \cdot 10^4$$$). The description of the test cases follows.

The first line of each test case contains four integers $$$n$$$, $$$k$$$, $$$x_D$$$, $$$y_D$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le n$$$): the number of circles, the number of point descriptions, and the coordinates of point $$$D$$$. Each of the next $$$k$$$ lines contains two integers $$$p$$$ and $$$q$$$ ($$$-n \le p \lt 2^{16}$$$, $$$0 \le q \lt 2^{16}$$$). If $$$p \ge 0$$$, these denote the coordinates of the next point $$$(p, q)$$$. If $$$p \lt 0$$$, you need to generate the next $$$|p|$$$ points as follows:

Let $$$f(x, y) = 2^{16}x + y$$$ and $$$T(x, y) = ((x \oplus \lfloor x \cdot 2^y\rfloor) + q) \bmod 2^{32}$$$. When generating $$$C_i$$$, we can obtain $$$f(C_i)$$$ as $$$(T(T(T(T(f(C_{i - 1}), 16), -11), 20), -24) \cdot 161120241) \bmod 2^{32}$$$, where $$$\oplus$$$ denotes the bitwise XOR operation, represented as ^ in many programming languages. If $$$i = 1$$$, use $$$C_0 = (0, 0)$$$ in this formula.

It is guaranteed that within any single test case, there are exactly $$$n + 1$$$ points, including the generated points and point $$$D$$$. All points satisfy $$$0 \le x, y \lt 2^{16}$$$, and for any $$$i = 1, 2, \ldots, n - 1$$$, it holds that $$$C_i \ne C_{i + 1}$$$. The sums of $$$n$$$ and $$$k$$$ across all test cases do not exceed $$$3 \cdot 10^6$$$ and $$$3 \cdot 10^4$$$, respectively.

Output

For each test case, print one real number: the greatest possible total area of the circles. Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-9}$$$.

Example
Input
2
3 3 0 0
2 0
2 2
0 2
2 1 51614 52212
-2 20449
Output
42.904272981
45769.863370150
Note

In the first test case, the radii of the optimal circles are approximately equal to 1.8478, 2.6131, and 1.8478.

In the second test case, the input points are $$$(51502, 52167)$$$ and $$$(51569, 52324)$$$.