P5916 [FJOI2014] Virus Defense Belt

As everyone knows, under the leadership of King Pang Ge, Country K is peaceful and prosperous like never before. But today, Country K has encountered an unprecedented crisis.

Within Country K, $n$ unknown viruses have been discovered at the same time. Each virus starts infecting the land of Country K from the position where it is discovered. Country K can be viewed as an infinite 2D plane, and the infected region of a virus can be viewed as a continuously expanding circular area. That is, at time $t$, the virus infects a circle of radius $t$, with the center at the discovery position of that virus. Fortunately, Country K has a unique virus defense belt that can kill these viruses. So King Pang Ge began disinfection work immediately after discovering the viruses. The so-called virus defense belt can be considered as a straight line, which can be placed at any position on the plane representing Country K. Once a virus touches this defense belt during its spread, it dies, and its infected land area becomes fixed as the area it occupied at the moment of death. Note that building the defense belt is very expensive, so Country K can build at most one virus defense belt. Now Pang Ge wants to know how to place this virus defense belt so that the average infected area of each virus is minimized, i.e. the total infected land area divided by the number of viruses $n$. Each virus can be considered independently, meaning the death of any one virus does not affect the others. Note that if the same region is infected by multiple viruses, it must be counted multiple times when computing the infected land area. For example, if one virus is discovered at $(0,0)$ and another at $(1,1)$, and both touch the defense belt and die at $t=1$, then the infected area of Country K at this time is $p_i\times2$, and the average infected area per virus is $p_i$. Since Country K has a world-class security monitoring system and public health protection system, you may assume that viruses start spreading only after the defense belt has been built. If a virus appears on the defense belt, its infected land area can be considered as $0$. Please write a program to output, under the optimal decision, the average infected area of these viruses.

The 1st line contains a positive integer $Q$, indicating how many test cases are in this dataset. For each test case, first input an integer $n$, indicating the number of viruses in this test case. Then one line contains two positive integers $x,y$, indicating the coordinates of the first virus. Then one line contains three positive integers $a,b,c$. If the coordinates of the $i$-th virus are $(x, y)$, then the coordinates of the $(i+1)$-th virus are $(x',y')$, where $x'=(a\times x^2+b\times x+c)\bmod107$, $y'=(a\times y^2+b\times y+c)\bmod107$. Here $\bmod$ is the modulo operator.

First output the sample index, then output, under the optimal decision, the land area of Country K that will be infected by these viruses. Print the answer with $5$ digits after the decimal point. See the output example for details. Please strictly follow the format in the output example.

For $100\%$ of the data, it holds that $0\le Q\times n \le 10^7$, $0\le x,y,a,b,c\le100$, $Q\le n$, $0