← 返回题目列表

AtCoder · geocon2013_c

C. 小偷

中文机器翻译题面 查看原题

問題文

你是一个小偷,生活在一个小而富裕的王国,周围环绕着河流和绿色植物。
新国王已经开始设置观察哨以提高安全性,所以你需要小心,不要被监视。
在岗哨处,我们检查谁在连接岗哨和其他岗哨的直线上。
您不能越过这条线或从其上的房屋中偷窃。
当然,你不能通过岗哨。
你会得到你想偷的房子的位置和哨所,所以看看你是否能从藏身处到达你想偷的房子而不被抓住。
不过,在偷窃时,你不会被抓到尚未设立的监视站。


入力

输入将以以下形式从标准输入给出。
N
S1 X1 Y1
S2 X2 Y2
...
SN XN YN
  • 第一行是一个整数,表示要抢劫的房屋和警卫室的总数。 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分:被抢劫的房屋不超过10万间,岗哨不超过10万个。

入力例 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