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