17899번 - Symmetric Polynomials 스페셜 저지다국어

A symmetric polynomial is a polynomial in n variables that remains the same polynomial under any permutation of the variables. For example, f(x₁, . . . , x_n) = x₁ + . . . + x_n is a symmetric polynomial (it is in fact called the first elementary symmetric polynomial). Symmetric polynomials have many important applications. They can, for instance, be used to prove that there is no formula for the roots of a general five-degree polynomial.

In this problem however, we will concern ourselves with another kind of symmetry. Consider an infinite curve P in the plane where both x and y coordinates are given by polynomials, i.e.,

x(t) = a_ntⁿ + a_n−1tⁿ⁻¹ + . . . + a₁t + a₀,

y(t) = b_mt^m + b_m−1t^m−1 + . . . + b₁t + b₀.

We say that such a curve is symmetric around a straight line L (given as an equation Ax + By + C = 0) if there exists a real number t₀ such that for all t ∈ R the point (x(t₀ + t), y(t₀ + t)) is the reflection of (x(t₀ − t), y(t₀ − t)) around the line L, and we call the line L a symmetry line for the curve P. For example, consider the curve P given by

x(t) = −5t⁵ − 26t⁴ − 19t³ + 59t² + 111t + 26,

y(t) = −t⁵ + 17t³ − 9t² − 61t + 12.

This curve is symmetric around the line 5x + y + 92 = 0 with t₀ = −1 (see Figure G.1).

Figure G.1: Illustration of Sample Input 1, drawn from t = −3.9 to t = 1.9.

Now, your task is to write a program that, given the two polynomials x(t) and y(t), finds a symmetry line of the curve (if one exists).

The first line of input contains an integer n (0 ≤ n ≤ 10), the degree of x. Then follows a line with n + 1 integers a_n, . . . , a₁, a₀, where a_i is the degree i coefficient of x. Then follow two lines describing the polynomial y in the same format.

If either of x(t) or y(t) is the zero polynomial, its degree is given as 0. The coefficients have absolute values bounded by 1 000. You may assume that the leading coefficient a_n of each polynomial is non-zero, except in the case when the polynomial is the zero polynomial.

Output three real numbers A, B and C, indicating that Ax + By + C = 0 is a symmetry line for the given curve. If there is no symmetry line, let A = B = C = 0. If the curve has more than one symmetry line, any one will be accepted.

In the case when a symmetry line exists, the provided line must satisfy the following conditions:

• 0.5 ≤ max(|A|, |B|) ≤ 10100 .
• The direction of the provided line is within 10⁻⁶ radians of some symmetry line.
• The value of C max(|A|,|B|) is correct within an absolute or relative error of 10⁻⁶.