prithivMLmods/Coder-Stat

1 2 3 4<H1>ねこまっしぐら</H1>5 6<p>7あるところに、高い塀に囲まれた大きなお屋敷がありました。そのお屋敷の主人は猫がとても大好きで、時折やってくる猫たちのために、いつもおいしいごはんを用意していました。お腹を空かせた猫たちは、高い塀をひょいと飛び越え、お屋敷の至る所に置いてあるごはんにまっしぐらに駆け寄るのでした。8</p>9 10<p>11ある日主人は、屋敷の中で何匹かの猫が倒れているのを見つけました。猫たちはごはんを探して屋敷の中を縦横無尽に走り回ったので、ぶつかったり転んだりしてしまったのです。主人は猫たちの安全を考えて、ごはんの置き場所を工夫することにしました。12</p>13 14<center>15<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_catGoingStraight">16</center>17 18<p>19上空から見ると、このお屋敷の塀は多角形をなしています。主人は猫たちがごはんを見つけやすいように、敷地内の中でも、多角形の頂点にあたる場所だけにごはんを置くことにしました。また猫たちは気まぐれなので、多角形の周上のどの点からお屋敷に入ってくるかは予想できません。そこで主人は、猫がどの点から入ったとしても、その点から直進していずれかのごはんにたどり着けるように、ごはんを配置することも決めました。20</p>21 22<p>23すべての頂点にごはんを配置すれば、この条件を満たすことができます。しかし、ごはんを補充して回るのは大変なので、主人はできるだけ少ない数の頂点にごはんを配置したいと思いました。さて、主人は最低何箇所にごはんを配置する必要があるでしょうか。24</p>25 26<p>27お屋敷の塀を表す多角形を入力とし、ごはんを配置する頂点の数の最小値を求めるプログラムを作成して下さい。ただし、猫は多角形の内部のみを直進できるものとします（辺は多角形の内部に含めるものとします）。28</p>29 30 31<h2>入力</h2>32 33<p>34入力は複数のデータセットからなる。入力の終わりはゼロ１つの行で示される。各データセットは以下の形式で与えられる。35</p>36 37<pre>38n39x<sub>1</sub> y<sub>1</sub>40x<sub>2</sub> y<sub>2</sub>41...42x<sub>n</sub> y<sub>n</sub>43</pre>44 45<p>46１行目に多角形の頂点の数 n (3 &le; n &le; 16) が与えられる。続く n 行に多角形の頂点の座標が与えられる。n 行のそれぞれは、１つの空白で区切られた２つの整数からなる。x<sub>i</sub> (-1000 &le; x<sub>i</sub> &le; 1000) は i 番目の頂点の x 座標、y<sub>i</sub> (-1000 &le; y<sub>i</sub> &le; 1000) は i 番目の頂点の y 座標を示す。多角形の頂点は、隣り合った頂点を反時計回りに訪問するような順番で与えられる。47</p>48 49<p>50データセットの数は 20 を超えない。51</p>52 53<h2>出力</h2>54<p>55各データセットごとに、ご飯を配置する頂点の数を１行に出力する。56</p>57 58 59<h2>入力例</h2>60 61<pre>628630 0643 2656 2668 6676 5687 7690 4703 4718720 0735 3745 2754 1766 1778 6786 4792 480081</pre>82 83 84<h2>出力例</h2>85 86<pre>87188289</pre>