Solving a Triangle

Time limit1sMemory limit128 MB

Summary

Given some sides and angles of a triangle, use the trigonometry identities to determine whether missing values are unique, finite-many, or impossible.

Level: Medium7 of 10
Topics: Geometry, Math, Implementation, Brute force
Solved: No attempts yet

Problem

A triangle in plane geometry is made of three sides and the three angles between them. Write the side lengths as $a$ , $b$ , $c$ , and write the angle opposite each side as $\alpha$ , $\beta$ , $\gamma$ , so $\alpha$ lies opposite $a$ , $\beta$ opposite $b$ , and $\gamma$ opposite $c$ .

Geometry books list many formulas for triangles.

\begin{aligned} \alpha + \beta + \gamma &= \pi \\ \frac{a}{\sin \alpha} = \frac{b}{\sin \beta} &= \frac{c}{\sin \gamma} \\ a &= b \cos \gamma + c \cos \beta \\ a^2 &= b^2 + c^2 - 2bc \cos \alpha \\ \frac{a - b}{a + b} &= \frac{\tan \frac{\alpha - \beta}{2}}{\tan \frac{\alpha + \beta}{2}} \end{aligned}

The six values $a$ , $\alpha$ , $b$ , $\beta$ , $c$ , $\gamma$ fully determine a triangle. Once enough of them are known, the formulas above give the rest.

Write a program that computes the missing values from a given subset. Some subsets say too little to fix a single triangle, and some describe no triangle at all. A valid triangle has all three sides greater than 0, and all three angles greater than 0 and less than $\pi$ . In those cases print Invalid input.. Print the same phrase when more than the minimal set is given but the values contradict each other, for example when all three angles are given and their sum exceeds $\pi$ . When more than the minimal set is given, a computed value $x$ and a given value $y$ agree when $|x - y| \le 10^{-6} \max(1, |x|, |y|)$ .

Other subsets admit more than one triangle, yet only finitely many. Then print More than one solution.

In every other case compute the missing values and print all six.

Input

The first line holds the number of parameter sets. Each following line holds six numbers separated by a single space: the values of $a$ , $\alpha$ , $b$ , $\beta$ , $c$ , and $\gamma$ , in that order. Angles are measured in radians. A value of -1 means the parameter is not given and has to be computed. Every floating-point number carries at least eight significant digits.

Output

Print one line per parameter set. When the values fix exactly one valid triangle, print $a$ , $\alpha$ , $b$ , $\beta$ , $c$ , $\gamma$ in that order, separated by single spaces. Round each value at the seventh decimal place and always print six digits after the decimal point, padding with zeros.

When more than one triangle fits and their number is finite, print More than one solution. When no single triangle is determined or no valid triangle exists, print Invalid input.

No value in the test data sits close enough to a sixth-decimal boundary for the rounding to be in doubt.

Examples2

Example 1

Input

3
62.72048064 2.26853639 -1.00000000 0.56794657 -1.00000000 -1.00000000
15.69326944 0.24714213 -1.00000000 1.80433105 66.04067877 -1.00000000
72.83685175 1.04409241 -1.00000000 -1.00000000 -1.00000000 -1.00000000

Expected output

62.720481 2.268536 44.026687 0.567947 24.587224 0.305110
Invalid input.
Invalid input.

Example 2

Input

5
3.00000000 -1.00000000 4.00000000 -1.00000000 5.00000000 -1.00000000
5.00000000 -1.00000000 7.00000000 -1.00000000 -1.00000000 1.00000000
5.00000000 0.50000000 8.00000000 -1.00000000 -1.00000000 -1.00000000
3.00000000 1.20000000 8.00000000 -1.00000000 -1.00000000 -1.00000000
3.00000000 0.64350111 4.00000000 0.92729522 5.00000000 1.57079633

Expected output

3.000000 0.643501 4.000000 0.927295 5.000000 1.570796
5.000000 0.774684 7.000000 1.366908 6.014885 1.000000
More than one solution.
Invalid input.
3.000000 0.643501 4.000000 0.927295 5.000000 1.570796