Yuekis' Audio Room

Time Limit : 1 sec, Memory Limit : 65536 KB

有益氏のオーディオルーム

数学者である有益氏の趣味は音楽鑑賞で、家に念願のオーディオルームを作りました。完成したオーディオルームで、友人を招いてお披露目会を開きたいと考えています。全員にできるだけ良い音で聴いてもらいたいので、部屋の中の何か所かで音を計測し、友人たちの位置での音の質を計算するつもりです。

計測点は、下の図の円弧と線分の交点である 1 番から 35 番までの点から選択します。1つの線分上にある点は、オーディオシステムからの距離が 100cmから 500cmまで 100cmずつ離れて並んでいます。1つの円弧状にある点は、もっとも右のもの(1 番から 5 番までの点)から反時計回りに、0°から 180° の範囲で 30°度刻みに並んでいます。


このような円弧と線分に囲まれた領域内のどこかに友人が居ることになるので、友人の居る位置によっ て必要な計測点を選択します。友人の位置は、円弧に沿って反時計回りに測った角度とオーディオシス テムからの距離で与えられます。必要な計測点は以下のように1点か、2点か、4点が選ばれます。

友人がちょうど計測点の位置にいれば、その1点を選びます。この図の例の場合、選ばれるのは 23 番の点です。
友人が円弧(または線分)の上にちょうど乗っていれば、その円弧(または線分)上にある、友人に最も近い2点を選びます。この図の例の場合、選ばれるのは 18 番と 23 番の点です。
友人が円弧と線分によって囲まれた区画の内側(円弧や線分の上ではない)にいれば、区画を作っている4点を選びます。この図の例の場合、選ばれるのは 17、18、22、23 番の点です。

有益氏を助けるために、必要な計測点の番号を求めるプログラムを作成してください。

入力

入力は以下の形式で与えられる。

N
r1 t1
r2 t2
:
rN tN

1行目に友人の数 N (1 ≤ N ≤ 50)が与えられる。続く N 行に、友人の位置が与えられる。友人の位置 ri (100 ≤ ri ≤ 500) はオーディオシステムからの距離を表す整数、ti (0 ≤ ti ≤ 180) は円弧に沿って反時計回りに測った角度を表す整数である。

出力

各友人の位置について、計測点の番号を昇順で1行に出力する。

入出力例

入力例

4
300 120
300 105
250 105
250 90

出力例

23
18 23
17 18 22 23
17 18

Source: PC Koshien 2014 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2014-11-8
http://web-ext.u-aizu.ac.jp/pc-concours/