prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem I:</font> Shy Polygons</H1>3 4<p>5You are given two solid polygons and their positions on the <i>xy</i>-plane. You can move one6of the two along the <i>x</i>-axis (they can overlap during the move). You cannot move it in other7directions. The goal is to place them as compactly as possible, subject to the following condition:8the distance between any point in one polygon and any point in the other must not be smaller9than a given minimum distance <i>L</i>.10</p>11<p>12We define the <i>width</i> of a placement as the difference between the maximum and the minimum13<i>x</i>-coordinates of all points in the two polygons.14</p>15<p>16Your job is to write a program to calculate the minimum width of placements satisfying the17above condition.18</p>19<p>20Let's see an example. If the polygons in Figure 13 are placed with <i>L</i> = 10.0, the result will be 100. Figure 14 shows one of the optimal placements.21</p>22 23<center>24<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_shyPolygons1">25</center>26 27 28<H2>Input</H2>29 30<p>31The input consists of multiple datasets. Each dataset is given in the following format.32</p>33<pre>34      <i>L</i>35      <i>Polygon</i><sub>1</sub>36      <i>Polygon</i><sub>2</sub>37</pre>38 39<center>40<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_shyPolygons2">41</center>42 43 44<p>45<i>L</i> is a decimal fraction, which means the required distance of two polygons. <i>L</i> is greater than460.1 and less than 50.0.47</p>48<p>49The format of each polygon is as follows.50</p>51 52<pre>53<i>n</i>54<i>x</i><sub>1</sub> <i>y</i><sub>1</sub>55<i>x</i><sub>2</sub> <i>y</i><sub>2</sub>56.57.58.59<i>x</i><sub><i>n</i></sub> <i>y</i><sub><i>n</i></sub>60</pre>61 62<p>63<i>n</i> is a positive integer, which represents the number of vertices of the polygon. <i>n</i> is greater than642 and less than 15.65</p>66<p>67Remaining lines represent the vertices of the polygon. A vertex data line has a pair of nonneg-68ative integers which represent the <i>x</i>- and y-coordinates of a vertex. <i>x</i>- and <i>y</i>-coordinates are69separated by a single space, and <i>y</i>-coordinate is immediately followed by a newline. <i>x</i> and <i>y</i> are70less than 500.71</p>72<p>73Edges of the polygon connect vertices given in two adjacent vertex data lines, and vertices given74in the last and the first vertex data lines. You may assume that the vertices are given in the75counterclockwise order, and the contours of polygons are simple, i.e. they do not cross nor touch76themselves.77</p>78<p>79Also, you may assume that the result is not sensitive to errors. In concrete terms, for a given80pair of polygons, the minimum width is a function of the given minimum distance <i>l</i>. Let us81denote the function <i>w</i>(<i>l</i>). Then you can assume that |<i>w</i>(<i>L</i> &plusmn; 10<sup>-7</sup>) - <i>w</i>(<i>L</i>)| &lt; 10<sup>-4</sup>.82</p>83<p>84The end of the input is indicated by a line that only contains a zero. It is not a part of a dataset.85</p>86 87 88 89<H2>Output</H2>90 91<p>92The output should consist of a series of lines each containing a single decimal fraction. Each93number should indicate the minimum width for the corresponding dataset. The answer should94not have an error greater than 0.0001. You may output any number of digits after the decimal95point, provided that the above accuracy condition is satisfied.96 97</p>98 99<H2>Sample Input</H2>100<pre>10110.523510231030 0104100 1001050 10010641070 5010820 5010920 801100 8011110.01124113120 45114140 35115140 65116120 5511781180 0119100 0120100 1001210 1001220 5512380 9012480 101250 4512610.012731280 01291 01300 113131320 1001331 1011340 10113510.013631370 01381 01390 10014031410 50142100 501430 511440145</pre>146 147<H2>Output for the Sample Input</H2>148<pre>149114.8824761501001511152110.5005153</pre>154 155 156 157