Hide

Problem Q
Smoothed Gardens

The Flathead Fancy Landscaping Company’s customers are too high-class to have gardens with straight edges so Joe P. Flathead, the owner, has come up with a way to smooth out the contours. He puts a stake in each corner of a triangular plot and drops a loop of rope around the three stakes. Then using a fourth stake in the loop, he pulls the rope tight to mark out a smoothed version of the triangle (see the figure below, the thinner lines are various positions of the rope). This process is similar to the method you learned in middle school to draw an ellipse using $2$ push-pins, a piece of string and a pencil, but J.P. Flathead is using three stakes (not two), a rope and another stake instead of a pencil.

\includegraphics[width=0.4\textwidth ]{jgardens-001.png}

The longer the rope loop, the smoother the outline will be (see the examples below):

\includegraphics[width=0.2\textwidth ]{jgardens-002.png} \includegraphics[width=0.15\textwidth ]{jgardens-003.png}

In order to determine how much soil and how many plants are required for the garden, Joe needs to find out the area of the resulting smoothed outline.

For this problem you will write a program which takes as input the coordinates of the corners of the triangle and the length of the rope loop and outputs the area of the smoothed region. The coordinate system will be chosen so that the first vertex is at the origin ($A(0, 0)$), the x-axis is along the line from the first vertex to the second vertex ($B(B_{x}, 0)$) and the final vertex is above the x-axis ($C(C_{x}, C_{y})$).

Input

The first line of input contains a single decimal integer $P$, ($1 \le P \le 10\, 000$), which is the number of data sets that follow. Each data set should be processed identically and independently.

Each data set consists of a single line of input. It contains the data set number, $K$, followed by a single space, followed by $4$ floating point values $B_ x$, $C_ x$, $C_ y$, ($0 < B_ x \le 100$, $0 < C_ y \le 100$, $-100 \le C_ x \le 100$), and the rope length $L$ ($L < 1\, 000$) all measured in feet. It is guaranteed that points $A$, $B$, $C$ form a triangle with a positive area. The length $L$ of the rope will be at least $0.05$ feet larger than the perimeter of this triangle. All floating numbers will be provided with no more than $3$ digits after the period.

Output

For each data set there is one line of output. The single output line consists of the data set number, $K$, followed by a single space followed by the area of the smoothed region in square feet. Your answer will be consider correct if its absolute error does not exceed $10^{-2}$.

Sample Input 1 Sample Output 1
3
1 4 0 3 13
2 3 -2 3 14.5
3 4 3 3 14
1 23.486243
2 37.460673
3 42.239747

Please log in to submit a solution to this problem

Log in