## REALROOT - Real Roots

In this problem you are challenged to factor the real roots of polynomials.

You are rewarded points based on the number of testcases you solve.

### Input

The first line contains the number of test cases, **T**.

The first line of each test case contains an integer **N**, the number of coeficients.

The second line contains the polynomial coeficients *a _{N-1}, ..., a_{1}, a_{0}* such that (

*).*

*P(x) = a*_{N-1}*x*^{N-1}*+ ... +**a*_{1}*x*^{1 }*+**a*_{0}*x*^{0}* *

*Output*

*Output*

* *

The roots of the polynomial, in sorted order. That is all real numbers *r _{0}, r_{1}, r_{2}, ...* such that

*P(r) = 0*.

* *

*Constrains*

**T**≤ 20**N**≤ 20- All coeficients are in the inclusive range [-10
^{6},10^{6}] - The output precision must be at least 2 decimal digits
- The roots must truly be real. No complex roots even if the imaginative part is very small.

*Cases*

- Same as the example
- ~3 random integer roots
- ~15 random integer roots
- ~10 Random interger coefficients
- ~10 Random floating point roots
- ~10 Random floating point coefficients
- Polynomials on the form
*p*_{0}=x, p_{k+1}=(p_{k}-a_{k})^2*e.g. ((x-3)^2-1)^2*

*Example*

*Example*

* *

Input:4 3 1 0 -2x3 1 0 1^{2}- 2x4 -1 3 -3 1^{2}+ 1-x7 1 -1 -9 13 8 -12 0^{3}+ 3x^{2}- 3x + 1x^{6}- x^{5}- 9x^{4}+ 13x^{3}+ 8x^{2}- 12x

Output:-1.414214 1.4142135-sqrt(2), sqrt(2)No real roots1 1 1Triple root in x=1-3 -1 0 1 2 2Mixed integer roots

*Notes*

- All testcases are double checked using Mathematica with 30 digits of precision.
- Constrains are set such that most approaches should be fine using double working precision.

hide comments

caopeng:
2014-06-12 20:50:21
What about duplicated root and what about no real root and why the description has a0x |

Added by: | Thomas Dybdahl Ahle |

Date: | 2012-06-06 |

Time limit: | 0.200s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 |