prithivMLmods/Coder-Stat

1 2<h3>Vampire</h3>3 4<p>5Mr. C is a vampire. If he is exposed to the sunlight directly, he turns 6into ash.7Nevertheless, last night, he attended to the meeting of Immortal and 8Corpse Programmers9Circle, and he has to go home in the near dawn.10Fortunately, there are many tall buildings around Mr. C's home, and 11while the sunlight is blocked by the buildings, he can move around 12safely.13The top end of the sun has just reached the horizon now.14In how many seconds does Mr. C have to go into his safe coffin?15</p>16 17<p>18To simplify the problem, we represent the eastern dawn sky as a 2-dimensional19<i>x</i>-<i>y</i> plane, where the <i>x</i> axis is horizontal and the <i>y</i> axis20is vertical, and approximate building silhouettes by rectangles21and the sun by a circle on this plane.22</p>23 24<p>25The <i>x</i> axis represents the horizon.26We denote the time by <i>t</i>, and the current time is <i>t</i>=0.27The radius of the sun is <i>r</i> and28its center is at (0, -<i>r</i>) when the time <i>t</i>=0.29The sun moves on the <i>x</i>-<i>y</i> plane in a uniform linear motion at30a constant velocity of (0, 1) per second.31</p>32 33<p>34The sunlight is blocked if and only if the entire region of the sun 35(including its edge) is included in the union of the silhouettes 36(including their edges) and the region below the horizon (y &#8804; 0).37</p>38 39<p>40Write a program that computes the time of the last moment when the sunlight is blocked.41</p>42 43<p>44The following figure shows the layout of silhouettes and the position of the sun at45the last moment when the sunlight is blocked, that corresponds to the46first dataset of Sample Input below. As this figure indicates, there are possibilities47that the last moment when the sunlight is blocked can be the time <i>t</i>=0.48</p>49 50<br>51<center>52<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_domestic2014_C_fig0" width="400px">53</center>54<br>55 56<p>57The sunlight is blocked even when two silhouettes share parts of their edges.58 59The following figure shows the layout of silhouettes and the position of the sun at the60last moment when the sunlight is blocked, corresponding to the second61dataset of Sample Input.62In this dataset the radius of the sun is 2 and there are two silhouettes:63the one with height 4 is in -2 &#8804; <i>x</i> &#8804; 0, and64the other with height 3 is in 0 &#8804; <i>x</i> &#8804; 2.65</p>66 67<br>68<center>69<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_domestic2014_C_fig1" width="400px">70</center>71<br>72 73 74<h3>Input</h3>75 76 77<p>78The input consists of multiple datasets.79The first line of a dataset contains two80integers <i>r</i> and <i>n</i> separated by a space.81<i>r</i> is the radius of the sun and <i>n</i> is the number of silhouettes82of the buildings.83(1 &#8804; <i>r</i> &#8804; 20, 0 &#8804; <i>n</i> &#8804; 20)84</p><p>85Each of following <i>n</i> lines contains three integers86<i>x<sub>li</sub></i>, <i>x<sub>ri</sub></i>, <i>h<sub>i</sub></i> (1 &#8804; <i>i</i> &#8804; <i>n</i>) separated by a space.87</p>88 89<p>90These three integers represent a silhouette rectangle of a building.91The silhouette rectangle is parallel to the horizon, and its left and right edges92are at <i>x</i> = <i>x<sub>li</sub></i> and <i>x</i> = <i>x<sub>ri</sub></i>, its top93edge is at <i>y</i> = <i>h<sub>i</sub></i>, and its bottom edge is on94the horizon.95(-20 &#8804; <i>x<sub>li</sub></i> &lt; <i>x<sub>ri</sub></i> &#8804; 20,960 &lt; <i>h<sub>i</sub></i> &#8804; 20)97</p><p>98The end of the input is indicated by a line containing two zeros separated by a space.99</p>100 101<p>102Note that these silhouettes may overlap one another.103</p>104 105 106<h3>Output</h3>107 108<p>109For each dataset, output a line containing the number indicating the time <i>t</i> of the last moment when the sunlight is blocked.110The value should not have an error greater than 0.001.111No extra characters should appear in the output.112</p>113 114 115<h3>Sample Input</h3>116 117<pre>2 3118-2 -1 31190 1 31202 3 31212 2122-2 0 41230 2 31242 6125-3 3 1126-2 3 2127-1 3 31280 3 41291 3 51302 3 61312 6132-3 3 1133-3 2 2134-3 1 3135-3 0 4136-3 -1 5137-3 -2 61380 0139</pre>140 141 142<h3>Output for the Sample Input</h3>143 144<pre>0.00001453.00001462.26791472.2679148</pre>