prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem H:</font> Top Spinning</H1>3 4<p>5Spinning tops are one of the most popular and the most traditional toys. Not only spinning6them, but also making one’s own is a popular enjoyment.7</p>8<p>9One of the easiest way to make a top is to cut out a certain shape from a cardboard and pierce10an axis stick through its center of mass. Professionally made tops usually have three dimensional11shapes, but in this problem we consider only two dimensional ones.12</p>13<p>14Usually, tops have rotationally symmetric shapes, such as a circle, a rectangle (with 2-fold15rotational symmetry) or a regular triangle (with 3-fold symmetry). Although such symmetries16are useful in determining their centers of mass, they are not definitely required; an asymmetric17top also spins quite well if its axis is properly pierced at the center of mass.18</p>19<p>20When a shape of a top is given as a path to cut it out from a cardboard of uniform thickness,21your task is to find its center of mass to make it spin well. Also, you have to determine whether22the center of mass is on the part of the cardboard cut out. If not, you cannot pierce the axis23stick, of course.24</p>25<!--26Java Specific: Submitted Java programs may not use classes implementing the interface27“java.awt.Shape”. You may use them for your debugging purposes.28-->29 30 31<H2>Input</H2>32 33<p>34The input consists of multiple datasets, each of which describes a counterclockwise path on a35cardboard to cut out a top. A path is indicated by a sequence of command lines, each of which36specifies a line segment or an arc.37</p>38<p>39In the description of commands below, the <i>current</i> position is the position to start the next cut,40if any. After executing the cut specified by a command, the <i>current position</i> is moved to the41end position of the cut made.42</p>43<p>44The commands given are one of those listed below. The command name starts from the first45column of a line and the command and its arguments are separated by a space. All the command46arguments are integers.47</p>48 49<pre>50start <i>x</i> <i>y</i>51</pre>52 53<p>54Specifies the start position of a path. This command itself does not specify any cutting;55it only sets the <i>current position</i> to be (<i>x</i>, <i>y</i>).56</p>57 58<pre>59line <i>x y</i>60</pre>61<p>62     Specifies a linear cut along a straight line from the <i>current position</i> to the position (<i>x</i>, <i>y</i>),63     which is not identical to the <i>current position</i>.64</p>65<pre>66arc <i>x y r</i>67</pre>68<p>69     Specifies a round cut along a circular arc. The arc starts from the <i>current position</i> and70     ends at (<i>x</i>, <i>y</i>), which is not identical to the <i>current position</i>. The arc has a radius of |<i>r</i>|.71     When <i>r</i> is negative, the center of the circle is to the left side of the direction of this round72     cut; when it is positive, it is to the right side (Figure 1). The absolute value of <i>r</i> is greater73     than the half distance of the two ends of the arc. Among two arcs connecting the start74     and the end positions with the specified radius, the arc specified is one with its central75     angle less than 180 degrees.76</p>77<pre>78close79</pre>80<p>81     Closes a path by making a linear cut to the initial start position and terminates a dataset.82     If the <i>current position</i> is already at the start position, this command simply indicates the83     end of a dataset.84</p>85 86<p>87The figure below gives an example of a command sequence and its corresponding path. Note88that, in this case, the given radius -<i>r</i> is negative and thus the center of the arc is to the left of89the arc. The arc command should be interpreted as shown in this figure and, not the other way90around on the same circle.91</p>92 93<center>94<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_topSpinning1">95<p>Figure 1: A partial command sequence and the path specified so far</p>96</center>97 98<p>99A dataset starts with a start command and ends with a close command.100</p>101<p>102The end of the input is specified by a line with a command end.103</p>104<p>105There are at most 100 commands in a dataset and at most 100 datasets are in the input.106Absolute values of all the coordinates and radii are less than or equal to 100.107</p>108<p>109You may assume that the path does not cross nor touch itself. You may also assume that paths110will never expand beyond edges of the cardboard, or, in other words, the cardboard is virtually111infinitely large.112</p>113 114<H2>Output</H2>115 116<p>117For each of the dataset, output a line containing <i>x</i>- and <i>y</i>-coordinates of the center of mass of118the top cut out by the path specified, and then a character ‘+’ or ‘-’ indicating whether this119center is on the top or not, respectively. Two coordinates should be in decimal fractions. There120should be a space between two coordinates and between the <i>y</i>-coordinate and the character ‘+’121or ‘-’. No other characters should be output. The coordinates may have errors less than 10<sup>-3</sup> .122You may assume that the center of mass is at least 10<sup>-3</sup> distant from the path.123 124</p>125 126 127<H2>Hints</H2>128 129<p>130An important nature of mass centers is that, when an object <i>O</i> can be decomposed into parts131<i>O</i><sub>1</sub> , . . . , <i>O</i><sub><i>n</i></sub> with masses <i>M</i><sub>1</sub> , . . . , <i>M</i><sub><i>n</i></sub> , the center of mass of <i>O</i> can be computed by:132</p>133 134<center>135<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_topSpinning2">136</center>137 138<p>139where <i>G<sub>k</sub></i> is the vector pointing the center of mass of <i>O<sub>k</sub></i>.140</p>141<p>142A circular segment with its radius <i>r</i> and angle <i>&theta;</i> (in radian) has its arc length <i>s</i> = <i>r&theta;</i> and its143chord length <i>c</i> = <i>r</i>&radic;(2 - 2cos<i>&theta;</i>). Its area size is <i>A</i> = <i>r</i><sup>2</sup>(<i>&theta;</i> - sin<i>&theta;</i>)/2 and its center of mass <i>G</i> is144<i>y</i> = 2<i>r</i><sup>3</sup>sin<sup>3</sup>(<i>&theta;</i>/2)/(3<i>A</i>) distant from the circle center.145</p>146 147 148<center>149<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_topSpinning3">150<p>Figure 2: Circular segment and its center of mass</p>151</center>152 153<center>154<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_topSpinning4">155<p>Figure 3: The first sample top</p>156</center>157 158 159<H2>Sample Input</H2>160<pre>161start 0 0162arc 2 2 -2163line 2 5164arc 0 3 -2165close166start -1 1167line 2 1168line 2 2169line -2 2170arc -3 1 -1171line -3 -2172arc -2 -3 -1173line 2 -3174line 2 -2175line -1 -2176line -1 -1177arc -1 0 2178close179start 0 0180line 3 0181line 5 -1182arc 4 -2 -1183line 6 -2184line 6 1185line 7 3186arc 8 2 -1187line 8 4188line 5 4189line 3 5190arc 4 6 -1191line 2 6192line 2 3193line 1 1194arc 0 2 -1195close196end197</pre>198 199<H2>Output for the Sample Input</H2>200<pre>2011.00000 2.50000 +202-1.01522 -0.50000 -2034.00000 2.00000 +204</pre>205