National Olympiad in Informatics, China, 2009

Little Z has been fond of mathematics ever since he was little. Being the smart fella he is, little Z really enjoys examining little problems in mathematics.

One day, little Z selected ~n~ points on a sheet of paper and connected all of them pair-by-pair, creating a total of ~\frac{n(n-1)}{2}~ line segments. Since the pencil is very sharp, we can consider the thickness of the line segments to be effectively ~0~.

Staring at these line segments, little Z fell into deep thought. He believed that a certain subset of these segments is of particular importance, and should be further examined. Thus, little Z took out his brush to retrace them. Applying his brush to the paper will produce a circle of radius ~r~. To trace a line segment, the tip of the brush (i.e. the center of the circle) starts at one endpoint, moving along the entire segment until it finally reaches the other endpoint. The figure below depicts a scenario with ~4~ points, where one line segment has already been traced.

Now, little Z would really like to know how large the total area of the traced region is. Can you help him answer this question?

Input Specification

There are 10 test cases path1.in ~ path10.in that will be given to your program (through standard input). They can be downloaded here for you to study: path.zip

Line ~1~ of input will contain two positive integers ~T~ and ~n~, respectively representing the test case number (between 1 and 10; the test case pathx.in will have ~T =~ x) and the number of points on the paper.
For lines ~2~ to ~n+1~, line ~i+1~ will contain two real numbers ~x_i~ and ~y_i~, indicating that the ~i~-th point has coordinates ~(x_i, y_i)~.
Line ~n+2~ will contain one positive integer ~m~, representing the number of line segments that little Z considers particularly important.
For lines ~n+3~ to ~n+m+2~, each line will contain two positive integers ~a~ and ~b~ to describe a line segment. Point ~a~ and point ~b~ will be its two endpoints.
Line ~n+m+3~ will contain a single real number ~r~, representing the radius of circle created by applying the brush to the paper.
Line ~n+m+4~ will contain 4 real numbers ~p_1~, ~p_2~, ~p_3~, and ~p_4~, the parameters used for grading.

Output Specification

The output should consist of one line with a single integer, the total area of the regions traced over by little Z's brush.

Sample Input

2
1 1
1 2
1
1 2
1
0.00001 0.001 0.1 1

Sample Output

5.1415927

Explanation

The scenario in the sample is depicted in the figure below.

Scoring

Each test case will be graded independently.
The 4 grading parameters ~p_1~, ~p_2~, ~p_3~, and ~p_4~ ~(p_1 < p_2 < p_3 < p_4)~ are provided for you in the input.
Your score for each test case will be determined as follows:

If your answer and the correct answer differ by no more than ~p_1~, then you will receive full points.
Otherwise, if your answer and the correct answer differ by no more than ~p_2~, then you will receive 70% of points.
Otherwise, if your answer and the correct answer differ by no more than ~p_3~, then you will receive 40% of points.
Otherwise, if your answer and the correct answer differ by no more than ~p_4~, then you will receive 10% of points.
Otherwise, you will be given a score of ~0~.

Problem translated to English by Alex.