prithivMLmods/Coder-Stat

1 2 3 4<H1>最後の扉</H1>5 6<p>7 秘境の地"ナラマンダ地方"<br>8 この奥深い洞窟に眠る黄金の伝説を求め、探検家ボブとマイクは様々な困難に立ち向かいました。ようやくたどり着いた最後の扉。この先には夢に見た黄金が待っています。9</p>10 11<p>12 その扉には多数の三角形が描かれていました。試しにマイクがその 1 つに触れてみると、その三角形は光を放ちました。光は三角形の底辺から垂直に頂点方向へ長方形を描きながら伸びていき、その先にある別の三角形に触れました。すると、光に触れた三角形も同じように光を放ち、それを繰り返していきました。13</p>14 15<p>16 扉の三角形は全て二等辺三角形(正三角形は含まない)で、どれも同じ大きさで、どれも重ならず（かつ触れることなく）、またどれも光は一定の距離だけ伸びていました。最後の三角形が光り終えると、そこには何事もなかったかのような静けさが戻ってきました。17</p>18 19<p>20 ボブは自分の足下に奇妙なメッセージを見つけました。<br>21 「むやみに触れるべからず。汝正しくこの扉に触れたとき、この扉は放たれん。  」22</p>23 24<p>25 ボブとマイクはこのメッセージの意味を考えながら、  何度も三角形に触れてみましたがなかなか扉は開きません。 しかし、それを繰り返していくうちに、二人はメッセージの意味がだんだん分かってきました。<br>26 「"むやみに触れるべからず"とは、扉に触れる回数は最小ということ。<br>27  できるだけ少ない回数で触れて、全ての三角形を光らせれば、きっと扉は開くはずだ!」<br>28</p>29 30<p>31例えば、扉には図 1 のように複数の二等辺三角形が描かれています。32</p>33 34<center>35<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_cave1"><br>36図 137</center>38<br>39 40<p>41 最初に左下の三角形に触れると、図 2 に示すように、その三角形の底辺から垂直に頂点方向へ光が放たれ、その光が触れる三角形が次々に光ります。42</p>43 44<center>45<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_cave2"><br>46図 247</center>48<br>49 50<p>51 次に左端の三角形に触れると、図 3 に示すように、全ての三角形が光ります。この手順が全ての三角形を光らせるための最少の手数(2 手)となります。52</p>53 54<center>55<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_cave3"><br>56<p>図 3</p>57</center>58 59<p>60  さあ、ボブとマイクが最後の扉を開ける手助けをしよう。61</p>62 63<p>64  扉に描かれている三角形の個数、光の伸びる長さ、それぞれの三角形の頂点の座標を入力とし、全ての三角形を光らせるために扉に触れる最少の回数を出力するプログラムを作成して下さい。光の伸びる長さは、底辺からの長さであるものとします。また、光はそれを放つ三角形の頂点を含むような十分な長さを持ちます。65</p>66 67<p>68  なお、この問題を解くにあたっては、2 点の距離が 0.01 以下の場合には、同一の点と処理します。また、1 点とひとつの直線の距離が 0.01 以下の場合には、この点はこの直線上にあるとして処理します。69</p>70 71<H2>Input</H2>72 73<p>74複数のデータセットの並びが入力として与えらる。入力の終わりはゼロふたつの行で示される。各データセットは以下の形式で与えらる。75</p>76 77<pre>78<var>n</var> <var>d</var>79<var>T<sub>1</sub></var>80<var>T<sub>2</sub></var>81:82<var>T<sub>n</sub></var>83</pre>84 85<p>86１行目に扉に描かれている三角形の個数 <var>n</var> (1 &le; <var>n</var> &le; 100) と光の伸びる長さを表す整数 <var>d</var> (1 &le; <var>d</var> &le; 1000) が与えられる。87</p>88 89<p>90続く <var>n</var> 行に各三角形の情報 <var>T<sub>i</sub></var> が以下の形式で与えられる。91</p>92 93<pre>94<var>x1</var> <var>y1</var> <var>x2</var> <var>y2</var> <var>x3</var> <var>y3</var>95</pre>96 97<p>98三角形の３つの頂点の座標が整数で与えられる(-1000 &le; <var>x1</var>, <var>y1</var>, <var>x2</var>, <var>y2</var>, <var>x3</var>, <var>y3</var> &le; 1000)。99</p>100 101<p>102データセットの数は 20 を超えない。103</p>104 105 106<H2>Output</H2>107 108<p>109データセットごとに、扉に触れる最少の回数を1行に出力する。110</p>111 112<H2>Sample Input</H2>113 114<pre>1153 41161 0 3 0 2 11172 3 2 5 3 41185 3 5 5 6 41193 21201 0 3 0 2 11212 3 2 5 3 41225 3 5 5 6 41230 0124</pre>125 126<H2>Output for the Sample Input</H2>127 128<pre>12911303131</pre>132 133 134