C - 泥棒 Editorial /

Time Limit: 5 sec / Memory Limit: 64 MB

問題文

あなたは、川と緑に囲まれた小さいながらも豊かな王国の泥棒です。
新しい王が治安向上のために監視所を設置し始めたので監視に引っかからないように気をつける必要があります。
監視所では他の監視所との間をまっすぐ結んだ線の上に誰がいるかを調べています。
あなたはこの線を横切ったり、線上の家に盗みに入ることはできません。
もちろん、監視所を通過することも出来ません
盗みに入る家と監視所の位置が与えられるので監視に引っかからずにアジトから盗みに入る家までたどり着けるか調べましょう。
ただし、盗みに入る段階でまだ設置されていない監視所について監視に引っかかることはありません。

入力

入力は以下の形式で標準入力から与えられる。 
N
S1 X1 Y1
S2 X2 Y2
...
SN XN YN
  • 1行目には盗みに入る家と監視所の数の合計を表す整数 N が与えられる。
  • 2行目からN+1行目には、盗みに入る家か監視所であるかを表す文字列 Si と、座標を表す整数 Xi Yi (1 ≦ i ≦ N , 1 ≦ Xi,Yi ≦ 108) が空白区切りで与えられる。
  • Si は TARGET もしくは MONITOR であり、それぞれ盗みに入る家と監視所を表している。
  • 盗みに入る家・監視所は全て違う位置にある。すなわち、 i ≠ j ならば (Xi,Yi) ≠ (Xj,Yj) を満たす。
  • 家に盗みに入る日時・監視所が設置される日時は入力で与えられる順の通りである。
    すなわち、ある家に盗みに入る時に既に設置されている監視所とはそれより前の入力で与えられた監視所のことである。
  • アジトは原点(0,0)にある。

出力

それぞれの盗みに入る家に対して入力の順に監視所に引っかからずに盗みに入れるかを判定し、監視に引っかからないなら SAFE 、引っかかるなら DANGER と出力すること。
各行の最後には改行を出力すること。

部分点

この問題は(1)〜(4)の部分点に分かれていて、それぞれ以下の条件を満たします。

  • (1) 50点 : 盗みに入る家は1箇所 監視所は3箇所以下
  • (2) 50点 : 盗みに入る家は100箇所以下 監視所は100箇所以下
  • (3) 50点 : 盗みに入る家は1000箇所以下 監視所は1000箇所以下
  • (4) 150点 : 盗みに入る家は100000箇所以下 監視所は100000箇所以下

入力例 1

4
MONITOR 1 1
MONITOR 5 1
MONITOR 1 5
TARGET 2 2

出力例 1

DANGER

どのように移動しても監視所をまっすぐ結んだ線の上を通らないと盗みに入ることはできません。

入力例 2

4
MONITOR 1 1
MONITOR 5 1
TARGET 2 2
MONITOR 1 5

出力例 2

SAFE

(1,5)に設置される３つ目の監視所が盗みに入るよりも後に設置されるので、監視に引っかからずに盗みに入ることができます。

入力例 3

7
MONITOR 2 1
MONITOR 4 1
MONITOR 6 1
TARGET 1 1
TARGET 3 1
TARGET 5 1
TARGET 7 1

出力例 3

SAFE
DANGER
DANGER
SAFE

監視所をまっすぐ結んだ線の上の家には盗みに入ることはできません。

入力例 4

16
TARGET 51120745 10211893
MONITOR 20328222 81595946
TARGET 24623254 3393748
MONITOR 96914389 5611093
MONITOR 26478507 21094604
MONITOR 38390485 52094021
MONITOR 54035108 52551113
MONITOR 32344389 92111226
MONITOR 42882326 49216313
TARGET 82009425 13194112
TARGET 36823977 72449795
TARGET 63951760 31282888
MONITOR 20099707 13753116
MONITOR 19673434 2381167
TARGET 135597 680580
TARGET 21578019 66062479

出力例 4

SAFE
SAFE
DANGER
DANGER
DANGER
SAFE
DANGER