prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem B:</font> How I Mathematician Wonder What You Are!</H1>3 4<p>5After counting so many stars in the sky in his childhood, Isaac, now an astronomer and a6mathematician, uses a big astronomical telescope and lets his image processing program count7stars. The hardest part of the program is to judge if a shining object in the sky is really a star.8As a mathematician, the only way he knows is to apply a mathematical definition of <i>stars</i>.9</p>10<p>11The mathematical defiition of a star shape is as follows: A planar shape <i>F</i> is <i>star-shaped</i> if and12only if there is a point C &isin; <i>F</i> such that, for any point P &isin; <i>F</i>, the line segment CP is contained13in <i>F</i>. Such a point C is called a center of <i>F</i>. To get accustomed to the definition, let's see some14examples below.15</p>16 17<center>18<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_howIMath">19<p>20Figure 2: Star shapes (the first row) and non-star shapes (the second row)21</p>22</center>23 24<p>25The firrst two are what you would normally call stars. According to the above definition, however,26all shapes in the first row are star-shaped. The two in the second row are not. For each star27shape, a center is indicated with a dot. Note that a star shape in general has infinitely many28centers. For example, for the third quadrangular shape, all points in it are centers.29</p>30<p>31Your job is to write a program that tells whether a given polygonal shape is star-shaped or not.32</p>33 34 35<H2>Input</H2>36 37<p>38The input is a sequence of datasets followed by a line containing a single zero. Each dataset39specifies a polygon, and is formatted as follows.40</p>41<pre>42        <i>n</i>43        <i>x</i><sub>1</sub> <i>y</i><sub>1</sub>44        <i>x</i><sub>2</sub> <i>y</i><sub>2</sub>45           ...46        <i>x</i><sub><i>n</i></sub> <i>y</i><sub><i>n</i></sub>47</pre>48 49<p>50The first line is the number of vertices, <i>n</i>, which satisfies 4 &le; <i>n</i> &le; 50. Subsequent <i>n</i> lines are the <i>x</i>- and <i>y</i>-coordinates of the <i>n</i> vertices. They are integers and satisfy 0 &le; <i>x<sub>i</sub></i> &le; 10000 and 0 &le; <i>y<sub>i</sub></i> &le; 10000 (<i>i</i> = 1, ...,  <i>n</i>). Line segments (<i>x<sub>i</sub></i>, <i>y<sub>i</sub></i>)-(<i>x</i><sub><i>i</i>+1</sub>, <i>y</i><sub><i>i</i>+1</sub>) (<i>i</i> = 1, ..., <i>n</i> - 1) and the line segment (<i>x<sub>n</sub></i>, <i>y<sub>n</sub></i>)-(<i>x</i><sub>1</sub>, <i>y</i><sub>1</sub>) form the border of the polygon in the counterclockwise order. That is, these line segments see the inside of the polygon in the left of their directions.51</p>52<p>53You may assume that the polygon is <i>simple</i>, that is, its border never crosses or touches itself.54You may also assume that no three edges of the polygon meet at a single point even when they55are infinitely extended.56</p>57 58<H2>Output</H2>59 60<p>61For each dataset, output "1" if the polygon is star-shaped and "0" otherwise. Each number must be in a separate line and the line should not contain any other characters.62</p>63 64<H2>Sample Input</H2>65<pre>6666766 136896 616976 987013 94714 07245 687387427 217555 147693 127756 957815 487938 468051 658164 3182083</pre>84 85<H2>Output for the Sample Input</H2>86<pre>87188089</pre>90 91 92 93 94