prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem D:</font> Digits on the Floor</H1>3 4<p>5Taro attempts to tell digits to Hanako by putting straight bars on the floor. Taro wants to6express each digit by making one of the forms shown in Figure 1.7</p>8 9<p>10Since Taro may not have bars of desired lengths, Taro cannot always make forms exactly as11shown in Figure 1. Fortunately, Hanako can recognize a form as a digit if the connection12relation between bars in the form is kept. Neither the lengths of bars nor the directions of forms13affect Hanako’s perception as long as the connection relation remains the same. For example,14Hanako can recognize all the awkward forms in Figure 2 as digits. On the other hand, Hanako15cannot recognize the forms in Figure 3 as digits. For clarity, touching bars are slightly separated16in Figures 1, 2 and 3. Actually, touching bars overlap exactly at one single point.17</p>18 19<center>20 21<table>22<tr><td><img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_digits1"></td></tr>23<tr><th>Figure 1: Representation of digits</th></tr>24</table>25<br>26 27<table>28<tr><td><img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_digits2"></td></tr>29<tr><th>Figure 2: Examples of forms recognized as digits</th></tr>30</table>31<br>32 33</center>34<p>35In the forms, when a bar touches another, the touching point is an end of at least one of them.36That is, bars never cross. In addition, the angle of such two bars is always a right angle.37</p>38<p>39To enable Taro to represent forms with his limited set of bars, positions and lengths of bars can40be changed as far as the connection relations are kept. Also, forms can be rotated.41</p>42<p>43Keeping the connection relations means the following.44</p>45 46<center>47 48<table>49<tr><td align="center"><img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_digits3"></td></tr>50<tr><th>Figure 3: Forms not recognized as digits (these kinds of forms are not contained in the dataset)</td></tr>51</table>52<br>53</center>54 55<ul>56<li>Separated bars are not made to touch.</li>57<li>Touching bars are not made separate.</li>58<li>When one end of a bar touches another bar, that end still touches the same bar. When it59touches a midpoint of the other bar, it remains to touch a midpoint of the same bar on60the same side.61</li>62<li>The angle of touching two bars is kept to be the same right angle (90 degrees and -9063degrees are considered different, and forms for 2 and 5 are kept distinguished).64</li>65</ul>66 67<p>68Your task is to find how many times each digit appears on the floor.69</p>70<p>71The forms of some digits always contain the forms of other digits. For example, a form for729 always contains four forms for 1, one form for 4, and two overlapping forms for 7. In this73problem, ignore the forms contained in another form and count only the digit of the “largest”74form composed of all mutually connecting bars. If there is one form for 9, it should be interpreted75as one appearance of 9 and no appearance of 1, 4, or 7.76 77</p>78 79<H2>Input</H2>80 81<p>82The input consists of a number of datasets. Each dataset is formatted as follows.83</p>84<p>85       <i>n</i><br>86       <i>x<sub>1a</sub>   y<sub>1a</sub>   x<sub>1b</sub>  y<sub>1b</sub></i><br>87       <i>x<sub>2a</sub>   y<sub>2a</sub>   x<sub>2b</sub>  y<sub>2b</sub></i><br>88                 .<br>89                 .<br>90                 .<br>91       <i>x<sub>na</sub>   y<sub>na</sub>   x<sub>nb</sub>  y<sub>nb</sub></i><br>92</p>93<p>94In the first line, <i>n</i> represents the number of bars in the dataset. For the rest of the lines, one95line represents one bar. Four integers <i>x<sub>a</sub></i>, <i>y<sub>a</sub></i> , <i>x<sub>b</sub></i> , <i>y<sub>b</sub></i> , delimited by single spaces, are given in96each line. <i>x<sub>a</sub></i> and <i>y<sub>a</sub></i> are the <i>x-</i> and <i>y-</i>coordinates of one end of the bar, respectively. <i>x<sub>b</sub></i> and97<i>y<sub>b</sub></i> are those of the other end. The coordinate system is as shown in Figure 4. You can assume981 &le; <i>n</i> &le; 1000 and 0 &le; <i>x<sub>a</sub></i> , <i>y<sub>a</sub></i> , <i>x<sub>b</sub></i> , <i>y<sub>b</sub></i> &le; 1000.99</p>100<p>101The end of the input is indicated by a line containing one zero.102</p>103 104<center>105<table>106<tr><td><img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_digits4"></td></tr>107<tr><th>Figure 4: The coordinate system</th></tr>108</table>109</center>110 111<p>112You can also assume the following conditions.113</p>114 115<ul>116<li>More than two bars do not overlap at one point.</li>117<li>Every bar is used as a part of a digit. Non-digit forms do not exist on the floor.</li>118<li>A bar that makes up one digit does not touch nor cross any bar that makes up another119digit.120</li>121<li>There is no bar whose length is zero.</li>122</ul>123 124<H2>Output</H2>125 126<p>127For each dataset, output a single line containing ten integers delimited by single spaces. These128integers represent how many times 0, 1, 2, . . . , and 9 appear on the floor in this order. Output129lines must not contain other characters.130 131</p>132 133<H2>Sample Input</H2>134<pre>135913660 140 200 300137300 105 330 135138330 135 250 215139240 205 250 215140298 167 285 15414130 40 30 9014230 90 150 90143150 90 150 2014430 40 150 401458146320 20 300 60147320 20 380 50148380 50 240 33014910 50 40 2015010 50 110 150151110 150 180 8015240 20 37 1715337 17 27 271542015572 222 132 182156204 154 204 54157510 410 520 370158404 54 204 54159530 450 410 450160204 68 404 6816180 110 120 30162130 160 180 60163520 370 320 320164310 360 320 320165120 30 180 6016660 100 80 110167404 154 204 15416880 60 60 100169430 550 590 550170510 410 310 360171430 450 430 550172404 54 404 154173232 202 142 262174142 262 102 2021750176</pre>177 178<H2>Output for the Sample Input</H2>179<pre>1800 1 0 1 0 0 0 0 0 11810 0 0 0 0 1 0 1 0 01821 0 1 0 2 0 0 0 1 0183</pre>184 185 186