prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem D:</font> Separate Points</H1>3 4<p>5Numbers of black and white points are placed on a plane. Let's imagine that a straight line6of infinite length is drawn on the plane. When the line does not meet any of the points, the7line divides these points into two groups. If the division by such a line results in one group8consisting only of black points and the other consisting only of white points, we say that the9line "separates black and white points".10</p>11 12<p>13Let's see examples in Figure 3. In the leftmost example, you can easily find that the black and14white points can be perfectly separated by the dashed line according to their colors. In the15remaining three examples, there exists no such straight line that gives such a separation.16</p>17 18<center>19<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_separatePoints"><br>20<p>Figure 3: Example planes</p>21</center>22 23<p>24In this problem, given a set of points with their colors and positions, you are requested to decide25whether there exists a straight line that separates black and white points.26</p>27 28 29<H2>Input</H2>30 31<p>32The input is a sequence of datasets, each of which is formatted as follows.33</p34 35<p>36     <i>n m</i><br>37     <i>x</i><sub>1</sub> <i>y</i><sub>1</sub><br>38     .<br>39     .<br>40     .<br>41     <i>x<sub>n</sub> y<sub>n</sub></i><br>42     <i>x</i><sub><i>n</i>+1</sub> <i>y</i><sub><i>n</i>+1</sub><br>43     .<br>44     .<br>45     .<br>46     <i>x</i><sub><i>n</i>+<i>m</i></sub> <i>y</i><sub><i>n</i>+<i>m</i></sub><br>47</p>48 49<p>50The first line contains two positive integers separated by a single space; <i>n</i> is the number of black51points, and <i>m</i> is the number of white points. They are less than or equal to 100. Then <i>n</i> + <i>m</i>52lines representing the coordinates of points follow. Each line contains two integers <i>x<sub>i</sub></i> and <i>y<sub>i</sub></i>53separated by a space, where (<i>x<sub>i</sub></i> , <i>y<sub>i</sub></i> ) represents the <i>x</i>-coordinate and the <i>y</i>-coordinate of the <i>i</i>-th54point. The color of the <i>i</i>-th point is black for 1 &le; i &le; <i>n</i>, and is white for <i>n</i> + 1 &le; <i>i</i> &le; <i>n</i> + <i>m</i>.55</p>56 57<p>58All the points have integral <i>x</i>- and <i>y</i>-coordinate values between 0 and 10000 inclusive. You can59also assume that no two points have the same position.60</p>61 62<p>63The end of the input is indicated by a line containing two zeros separated by a space.64 65</p>66 67<H2>Output</H2>68 69<p>70For each dataset, output "<span>YES</span>" if there exists a line satisfying the condition. If not, output71"<span>NO</span>". In either case, print it in one line for each input dataset.72 73</p>74 75<H2>Sample Input</H2>76<pre>773 378100 70079200 20080600 60081500 10082500 30083800 500843 385100 30086400 60087400 10088600 40089500 90090300 300913 492300 30093500 30094400 60095100 10096200 90097500 90098800 100991 2100300 300101100 100102500 5001031 1104100 100105200 1001062 21070 0108500 7001091000 14001101500 21001112 21120 01131000 10001141000 01150 10001163 31170 1001184999 10211910000 1031205001 10212110000 1021220 1011233 3124100 100125200 100126100 2001270 0128400 01290 4001303 31312813 16401322583 28921332967 1916134541 35621359298 36861367443 79211370 0138 139</pre>140 141<H2>Output for the Sample Input</H2>142<pre>143YES144NO145NO146NO147YES148YES149NO150NO151NO152YES153</pre>154