This page is still under construction.

Parts of this page are still being built. What you see may change.

Solving cubic equations 2

Interview

Time limit2sMemory limit512 MB

Summary
Find all real roots of a cubic with rational coefficients, printing them rounded to four decimals, using that at least one root is an integer.
Level

Medium7 of 10

Topics
Math, Binary search, Implementation, Number theory
Solved
No attempts yet

Problem

Write a program that finds every real root of the cubic equation Ax3+Bx2+Cx+D=0Ax^3 + Bx^2 + Cx + D = 0.

Every equation in the input has at least one integer root.

The absolute value of AA, BB, CC, and DD is at most 2×1062 \times 10^6, and AA is not zero. Every real root has absolute value at most 10610^6. AA, BB, CC, and DD can carry up to 11 digits after the decimal point. Within one equation, two different roots differ by more than 10−910^{-9}.

Input

The first line contains the number of test cases NN (0<N<1000 < N < 100). Each of the next NN lines contains the coefficients AA, BB, CC, and DD of one equation, separated by spaces.

Output

For each equation, print all of its real roots in ascending order on one line. Separate two roots with a single space and round each root to four digits after the decimal point. Print a multiple root only once. If a root rounds to zero, print 0.0000 and not -0.0000.

Examples2

  1. Example 1

    Input
    3
    1.5 -5 2 -1.5
    2 -7 7 -2
    2 0 0 0
    
    Expected output
    3.0000
    0.5000 1.0000 2.0000
    0.0000
    
  2. Example 2

    Input
    4
    1 -1 -2 2
    -1 0 0 1
    1 -15 75 -125
    1 -1 -8 12
    
    Expected output
    -1.4142 1.0000 1.4142
    1.0000
    5.0000
    -3.0000 2.0000