Задачі
Digits on the Floor
Digits on the Floor
Taro attempts to tell digits to Hanako by putting straight bars on the floor. Taro wants to express each digit by making one of the forms shown in \textit{\textbf{Figure 1}}.
Since Taro may not have bars of desired lengths, Taro cannot always make forms exactly as shown in \textit{\textbf{Figure 1}}. Fortunately, Hanako can recognize a form as a digit if the connection relation between bars in the form is kept. Neither the lengths of bars nor the directions of forms affect Hanako’s perception as long as the connection relation remains the same. For example, Hanako can recognize all the awkward forms in \textit{\textbf{Figure 2}} as digits. On the other hand, Hanako cannot recognize the forms in \textit{\textbf{Figure 3}} as digits. For clarity, touching bars are slightly separated in\textit{\textbf{Figures 1}}, \textit{\textbf{2}} and \textit{\textbf{3}}. Actually, touching bars overlap exactly at one single point.
\includegraphics{https://static.e-olymp.com/content/72/724b8aa06ff98b6562a3c2f795ce70b04954ce2b.jpg}
\textit{\textbf{Figure 1}}: Representation of digits
\includegraphics{https://static.e-olymp.com/content/82/82fd16052fe0ccbb9d9ecabf8cdb92717d9770fd.jpg}
\textit{\textbf{Figure 2}}: Examples of forms recognized as digits
In the forms, when a bar touches another, the touching point is an end of at least one of them. That is, bars never cross. In addition, the angle of such two bars is always a right angle.
To enable Taro to represent forms with his limited set of bars, positions and lengths of bars can be changed as far as the connection relations are kept. Also, forms can be rotated.
Keeping the connection relations means the following.
\includegraphics{https://static.e-olymp.com/content/59/595c755715d88a52b6208598b815c6393b296da8.jpg}
\textit{\textbf{Figure 3}}: Forms not recognized as digits (these kinds of forms are not contained in the dataset)
\begin{itemize}
\item Separated bars are not made to touch.
\item Touching bars are not made separate.
\item When one end of a bar touches another bar, that end still touches the same bar. When it touches a midpoint of the other bar, it remains to touch a midpoint of the same bar on the same side.
\item The angle of touching two bars is kept to be the same right angle (\textbf{90} degrees and \textbf{−90} degrees are considered different, and forms for \textbf{2} and \textbf{5} are kept distinguished).
\end{itemize}
Your task is to find how many times each digit appears on the floor.
The forms of some digits always contain the forms of other digits. For example, a form for \textbf{9} always contains four forms for \textbf{1}, one form for \textbf{4}, and two overlapping forms for \textbf{7}. In this problem, ignore the forms contained in another form and count only the digit of the "largest" form composed of all mutually connecting bars. If there is one form for\textbf{9}, it should be interpreted as one appearance of \textbf{9} and no appearance of \textbf{1}, \textbf{4}, or \textbf{7}.
\InputFile
The input consists of a number of datasets. Each dataset is formatted as follows.
\textbf{n}
\textbf{x_1a y_1a x_1b y_1b}
\textbf{x_2a y_2a x_2b y_2b}
\textbf{...}
\textbf{x_na y_na x_nb x_nb}
In the first line, \textbf{n} represents the number of bars in the dataset. For the rest of the lines, one line represents one bar. Four integers \textbf{x_a}, \textbf{y_a}, \textbf{x_b}, \textbf{y_b}, delimited by single spaces, are given in each line. \textbf{x_a} and \textbf{y_a} are the \textbf{x}- and \textbf{y}-coordinates of one end of the bar, respectively. \textbf{x_b} and \textbf{y_b} are those of the other end. The coordinate system is as shown in \textit{\textbf{Figure 4}}. You can assume \textbf{1} ≤ \textbf{n} ≤ \textbf{1000} and \textbf{0} ≤ \textbf{x_a}, \textbf{y_a}, \textbf{x_b}, \textbf{y_b} ≤ \textbf{1000}.
The end of the input is indicated by a line containing one zero.
\includegraphics{https://static.e-olymp.com/content/27/279a853a10439e9b20f8b43e0d8fe689ca26690f.jpg}
\textit{\textbf{Figure 4}}: The coordinate system
You can also assume the following conditions.
\begin{itemize}
\item More than two bars do not overlap at one point.
\item Every bar is used as a part of a digit. Non-digit forms do not exist on the floor.
\item A bar that makes up one digit does not touch nor cross any bar that makes up another digit.
\item There is no bar whose length is zero.
\end{itemize}
\OutputFile
For each dataset, output a single line containing ten integers delimited by single spaces. These integers represent how many times \textbf{0}, \textbf{1}, \textbf{2}, ..., and \textbf{9} appear on the floor in this order. Output lines must not contain other characters.
Вхідні дані #1
9 60 140 200 300 300 105 330 135 330 135 250 215 240 205 250 215 298 167 285 154 30 40 30 90 30 90 150 90 150 90 150 20 30 40 150 40 8 320 20 300 60 320 20 380 50 380 50 240 330 10 50 40 20 10 50 110 150 110 150 180 80 40 20 37 17 37 17 27 27 20 72 222 132 182 204 154 204 54 510 410 520 370 404 54 204 54 530 450 410 450 204 68 404 68 80 110 120 30 130 160 180 60 520 370 320 320 310 360 320 320 120 30 180 60 60 100 80 110 404 154 204 154 80 60 60 100 430 550 590 550 510 410 310 360 430 450 430 550 404 54 404 154 232 202 142 262 142 262 102 202 0
Вихідні дані #1
0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 2 0 0 0 1 0