AT_geocon2013_c 泥棒

[problemUrl]: https://atcoder.jp/contests/geocon2013/tasks/geocon2013_c あなたは、川と緑に囲まれた小さいながらも豊かな王国の泥棒です。 新しい王が治安向上のために監視所を設置し始めたので監視に引っかからないように気をつける必要があります。 監視所では他の監視所との間をまっすぐ結んだ線の上に誰がいるかを調べています。 あなたはこの線を横切ったり、線上の家に盗みに入ることはできません。 もちろん、監視所を通過することも出来ません 盗みに入る家と監視所の位置が与えられるので監視に引っかからずにアジトから盗みに入る家までたどり着けるか調べましょう。 ただし、盗みに入る段階でまだ設置されていない監視所について監視に引っかかることはありません。 入力は以下の形式で標準入力から与えられる。 > $ 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箇所以下 ``` 4 MONITOR 1 1 MONITOR 5 1 MONITOR 1 5 TARGET 2 2 ``` ``` DANGER ``` ``` 4 MONITOR 1 1 MONITOR 5 1 TARGET 2 2 MONITOR 1 5 ``` ``` SAFE ``` (1,5)に設置される３つ目の監視所が盗みに入るよりも後に設置されるので、監視に引っかからずに盗みに入ることができます。 ``` 7 MONITOR 2 1 MONITOR 4 1 MONITOR 6 1 TARGET 1 1 TARGET 3 1 TARGET 5 1 TARGET 7 1 ``` ``` SAFE DANGER DANGER SAFE ``` 監視所をまっすぐ結んだ線の上の家には盗みに入ることはできません。 ``` 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 ``` ``` SAFE SAFE DANGER DANGER DANGER SAFE DANGER ```

N/A

N/A