prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem H:</font> Monster Trap</H1>3 4<p>5Once upon a time when people still believed in magic, there was a great wizard Aranyaka6Gondlir. After twenty years of hard training in a deep forest, he had finally mastered ultimate7magic, and decided to leave the forest for his home.8</p>9<p>10Arriving at his home village, Aranyaka was very surprised at the extraordinary desolation. A11gloom had settled over the village. Even the whisper of the wind could scare villagers. It was a12mere shadow of what it had been.13</p>14<p>15What had happened? Soon he recognized a sure sign of an evil monster that is immortal. Even16the great wizard could not kill it, and so he resolved to seal it with magic. Aranyaka could cast17a spell to create a monster trap: once he had drawn a line on the ground with his magic rod,18the line would function as a barrier wall that any monster could not get over. Since he could19only draw straight lines, he had to draw several lines to complete a monster trap, i.e., magic20barrier walls enclosing the monster. If there was a gap between barrier walls, the monster could21easily run away through the gap.22</p>23<p>24For instance, a complete monster trap without any gaps is built by the barrier walls in the left25figure, where “M” indicates the position of the monster. In contrast, the barrier walls in the26right figure have a loophole, even though it is almost complete.27</p>28 29<center>30<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_monsterTrap">31</center>32 33<p>34Your mission is to write a program to tell whether or not the wizard has successfully sealed the35monster.36</p>37 38<H2>Input</H2>39 40<p>41The input consists of multiple data sets, each in the following format.42</p>43 44<pre>45<i>n</i>46<i>x</i><sub>1</sub> <i>y</i><sub>1</sub>  <i>x'</i><sub>1</sub> <i>y'</i><sub>1</sub>47<i>x</i><sub>2</sub> <i>y</i><sub>2</sub>  <i>x'</i><sub>2</sub> <i>y'</i><sub>2</sub>48      ...49<i>x</i><sub><i>n</i></sub> <i>y</i><sub><i>n</i></sub>  <i>x'</i><sub><i>n</i></sub> <i>y'</i><sub><i>n</i></sub>50</pre>51 52<p>53The first line of a data set contains a positive integer n, which is the number of the line segments54drawn by the wizard. Each of the following <i>n</i> input lines contains four integers <i>x</i>, <i>y</i>, <i>x'</i>, and55<i>y'</i>, which represent the <i>x</i>- and <i>y</i>-coordinates of two points (<i>x</i>, <i>y</i>) and (<i>x'</i>, <i>y'</i> ) connected by a line56segment. You may assume that all line segments have non-zero lengths. You may also assume57that <i>n</i> is less than or equal to 100 and that all coordinates are between -50 and 50, inclusive.58</p>59<p>60For your convenience, the coordinate system is arranged so that the monster is always on the61origin (0, 0). The wizard never draws lines crossing (0, 0).62</p>63<p>64You may assume that any two line segments have at most one intersection point and that no65three line segments share the same intersection point. You may also assume that the distance66between any two intersection points is greater than 10<sup>-5</sup>.67</p>68<p>69An input line containing a zero indicates the end of the input.70</p>71 72 73<H2>Output</H2>74 75<p>76For each data set, print “yes” or “no” in a line. If a monster trap is completed, print “yes”.77Otherwise, i.e., if there is a loophole, print “no”.78</p>79 80<H2>Sample Input</H2>81<pre>82883-7 9 6 984-5 5 6 585-10 -5 10 -586-6 9 -9 -6876 9 9 -688-1 -2 -3 10891 -2 3 1090-2 -3 2 -391892-7 9 5 793-5 5 6 594-10 -5 10 -595-6 9 -9 -6966 9 9 -697-1 -2 -3 10981 -2 3 1099-2 -3 2 -31000101</pre>102 103<H2>Output for the Sample Input</H2>104<pre>105yes106no107</pre>108 109