prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem H: </font>Don't Burst the Balloon</H1>3 4<p>5An open-top box having a square bottom is placed on the floor. You see a number of needles vertically planted on its bottom.6</p>7 8<p>9You want to place a largest possible spheric balloon touching the box bottom, interfering with none of the side walls nor the needles.10</p>11 12<p>13<b>Java Specific:</b> Submitted Java programs may not use "java.awt.geom.Area". You may use it for your debugging purposes.14</p>15 16<p>17Figure H.1 shows an example of a box with needles and the corresponding largest spheric balloon. It corresponds to the first dataset of the sample input below.18</p>19 20 21<center>22<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_dontBurstTheBalloon" style="aling:center"><br/>23<span>24Figure H.1. The upper shows an example layout and the lower shows the largest spheric balloon that can be placed.25</span>26</center>27<br/>28 29 30<H2>Input</H2>31 32<p>33The input is a sequence of datasets. Each dataset is formatted as follows.34</p>35 36<pre>37<var>n</var> <var>w</var>38<var>x<sub>1</sub></var> <var>y<sub>1</sub></var> <var>h<sub>1</sub></var>39:40<var>x<sub>n</sub></var> <var>y<sub>n</sub></var> <var>h<sub>n</sub></var>41</pre>42 43<p>44The first line of a dataset contains two positive integers, <var>n</var> and <var>w</var>, separated by a space. <var>n</var> represents the number of needles, and <var>w</var> represents the height of the side walls.45</p>46 47<p>48The bottom of the box is a 100 &times; 100 square. The corners of the bottom face are placed at positions (0, 0, 0), (0, 100, 0), (100, 100, 0), and (100, 0, 0).49</p>50 51<p>52Each of the <var>n</var> lines following the first line contains three integers, <var>x<sub>i</sub></var>, <var>y<sub>i</sub></var>, and <var>h<sub>i</sub></var>. (<var>x<sub>i</sub></var>, <var>y<sub>i</sub></var>, 0) and <var>h<sub>i</sub></var> represent the base position and the height of the <var>i</var>-th needle. No two needles stand at the same position.53</p>54 55<p>56You can assume that 1 &le; <var>n</var> &le; 10, 10 &le; <var>w</var> &le; 200, 0 &lt; <var>x<sub>i</sub></var> &lt; 100, 0 &lt; <var>y<sub>i</sub></var> &lt; 100 and 1 &le; <var>h<sub>i</sub></var> &le; 200. You can ignore the thicknesses of the needles and the walls.57</p>58 59<p>60The end of the input is indicated by a line of two zeros. The number of datasets does not exceed 1000.61</p>62 63<H2>Output</H2>64 65<p>66For each dataset, output a single line containing the maximum radius of a balloon that can touch the bottom of the box without interfering with the side walls or the needles. The output should not contain an error greater than 0.0001.67</p>68 69<H2>Sample Input</H2>70<pre>715 167270 66 407338 52 207440 35 107570 30 107620 60 10771 1007854 75 200791 108090 10 1811 118254 75 200833 108453 60 18561 38 18645 48 1874 108820 20 108920 80 109080 20 109180 80 10920 093</pre>94 95<H2>Output for the Sample Input</H2>96<pre>9726.000009839.0000099130.0000010049.4977710185.0000010295.00000103</pre>