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_kochi" width="380">16</center>17<br/>18 19 20<p>21図のように、花の香りは扇状に広がり、その領域は風の向かう方向と強さによって決まる。扇形は風の向かう方向 w を中心にして対称に広がり、風の強さ a を半径とする領域をもつ。香りが広がる角度 d は花の種類によって決まっているが、風の向かう方向と強さは日によって異なる。ただし、同じ日では、すべての場所で風の向かう方向と強さは同じである。22</p>23 24<p>25手元には、私の梅以外の梅・桃・桜の位置と花の種類ごとの香りが広がる角度、引っ越し先の家の候補のデータがある。さらに、数日分の風の向かう方向と強さのデータもある。私の梅以外の梅・桃・桜の木と家の位置は、私の梅の位置を原点とした座標で示されている。26</p>27 28<p>29これらのデータを使って、私の梅の香りだけが届く日数の最も多い家を探すためのプログラムを書いてみることとしよう。私は有能なプログラマーなのだから！30</p>31 32 33<h2>入力</h2>34 35<p>36入力は複数のデータセットからなる。入力の終わりはゼロ２つの行で示される。各データセットは以下の形式で与えられる。37</p>38 39<pre>40H R41hx<sub>1</sub> hy<sub>1</sub>42hx<sub>2</sub> hy<sub>2</sub>43:44hx<sub>H</sub> hy<sub>H</sub>45U M S du dm ds46ux<sub>1</sub> uy<sub>1</sub>47ux<sub>2</sub> uy<sub>2</sub>48:49ux<sub>U</sub> uy<sub>U</sub>50mx<sub>1</sub> my<sub>1</sub>51mx<sub>2</sub> my<sub>2</sub>52:53mx<sub>M</sub> my<sub>M</sub>54sx<sub>1</sub> sy<sub>1</sub>55sx<sub>2</sub> sy<sub>2</sub>56:57sx<sub>S</sub> sy<sub>S</sub>58w<sub>1</sub> a<sub>1</sub>59w<sub>2</sub> a<sub>2</sub>60:61w<sub>R</sub> a<sub>R</sub>62</pre>63 64<p>65各行で与えられる数値は１つの空白で区切られている。66</p>67 68<p>69１行目に引っ越し先の家の候補の数 H (1 &le; H &le; 100) と風の記録の数 R (1 &le; R &le; 100) が与えられる。続くH 行に引っ越し先の家の位置が与えられる。hx<sub>i</sub> とhy<sub>i</sub>は i 番目の家の x 座標と y 座標を示す-1000 以上1000 以下の整数である。70</p>71 72<p>73続く１行に、私の梅以外の梅の木の数 U と、桃・桜の木の数 M、S、梅・桃・桜の香りが広がる角度du、dm、ds が与えられる。U、M、S の範囲は 0 以上10 以下である。角度の単位は度であり、1 以上180 未満の整数である。74<?p>75 76続く U 行に私の梅以外の梅の木の位置、続く M 行に桃の木の位置、続く S 行に桜の木の位置が与えられる。uxi と uyi、mxi と myi、sxi と syi はそれぞれ、i 番目の梅・桃・桜の木の x 座標と y 座標を示す、-1000 以上 1000 以下の整数である。77</p>78 79<p>80続く R 行に風の記録が与えられる。w<sub>i</sub> (0 &le; w<sub>i</sub> &lt; 360) と a<sub>i</sub>(0 &lt; a<sub>i</sub> &le; 100) は i 日目の風の向かう方向と強さを表す整数である。風の向かう方向は、x 軸の正の向きから反時計回りに測った角度で表し、単位は度とする。81</p>82 83<p>84入力は以下の条件を満たすと考えてよい。85</p>86<ul>87<li> 入力される座標はすべて異なるものとする。</li>88<li> 原点には私の梅以外無い。</li>89<li> どの花についても、花の香りが届く領域の境界から距離が 0.001 以内には家は無い。</li>90</ul>91 92<p>93データセットの数は 50 を超えない。94</p>95 96 97<h2>出力</h2>98<p>99データセットごとに、私の梅の香りだけが届く日数の最も多い全ての家の番号を、小さい順に１行に出力する。家の番号の間は空白１つで区切る。行の終わりには空白文字を出力しない。100</p>101 102<p>103ただし、どの家についても、私の梅の花の香りだけが届く日が１日もなければ、NA と出力する。104</p>105 106 107<h2>入力例</h2>108 109<pre>1106 31112 11121 21135 21141 31151 5116-2 31171 1 1 90 30 451183 -4119-3 01202 -212145 612290 6123135 61242 11251 31265 21270 1 1 90 30 45128-3 01292 -213045 61310 0132</pre>133 134 135<h2>出力例</h2>136 137<pre>1385 6139NA140</pre>