35103번 - Number of Faces 다국어

Two planes, $H_1$ and $H_2$, are in a three-dimensional Euclidean space with axes, $x$, $y$, and $z$, where $H_1$ is defined by $z = 1$ and $H_2$ by $z = 2$.

You are given $n$ real numbers, $d_1, \dots , d_n$, and $m$ real numbers, $d'_1 , \dots , d'_m$. These real numbers are positive and strictly less than $180$. Consider drawing the following convex polygons on the planes $H_1$ and $H_2$.

• On $H_1$, you draw an $n$-sided polygon. The interior angles at its vertices are $d_1, \dots , d_n$ degrees in counterclockwise order as viewed from the origin.
• Similarly, on $H_2$, you draw an $m$-sided polygon. The interior angles at its vertices are $d'_1 , \dots , d'_m$ degrees in counterclockwise order as viewed from the origin.

Here, only the interior angles of the polygons are specified; the lengths of their edges and the positions of their vertices are not.

Once the positions of the two polygons are fixed, the convex polyhedron whose vertex set is these $n+ m$ vertices is uniquely determined. Write a program that enumerates all the possible numbers of faces that such a convex polyhedron can have.

Here, all the dihedral angles (angles between two adjacent faces) of a convex polyhedron must be strictly less than $180$ degrees.

In the first test case of Sample Input 1, quadrilaterals whose interior angles are all $90$ degrees are drawn on $H_1$ and $H_2$. For example, a rectangular cuboid can be constructed as in Figure G.1 (a), which has six faces. By rotating one of the quadrilaterals as shown in Figure G.1 (b), a convex polyhedron with ten faces can be constructed. The possible numbers of faces are six and ten.

Figure G.1. The first test case of Sample Input 1

The input consists of at most $50$ test cases, each in the following format.

$n$

$d_1$

$\vdots$

$d_n$

$m$

$d'_1$

$\vdots$

$d'_m$

The integer $n$ represents the number of vertices of the polygon drawn on $H_1$ ($3 ≤ n ≤ 50$). The real numbers, $d_1, \dots , d_n$, represent the interior angles. They are at least $10^{−9}$ and strictly less than $180$, and are given with exactly nine digits after the decimal point. They satisfy $d_1 + \cdots + d_n = (n − 2) \times 180$.

Similarly, the integer $m$ represents the number of vertices of the polygon drawn on $H_2$ ($3 ≤ m ≤ 50$). The real numbers, $d'_1 , \dots , d'_m$, represent the interior angles. They are at least $10^{−9}$ and strictly less than $180$, and are given with exactly nine digits after the decimal point. They satisfy $d'_1 + \cdots + d'_m = (m − 2) \times 180$.

The end of the input is indicated by a line consisting only of a zero.

For each test case, output in a line all possible numbers of faces that the convex polyhedron can have, in ascending order, separated by a space.