AT_geocon2013_c 泥棒

你是一名生活在被河流和绿地环绕的小而富饶王国里的盗贼。 由于新国王为了提升治安开始设立监视所，你需要小心不要被监视发现。 监视所会检查与其他监视所之间直线连接上的所有人员。 你不能穿越这些直线，也不能潜入位于这些直线上的房屋。 当然，你也不能经过监视所本身。 给定你要潜入的房屋和监视所的位置，请判断你是否能从据点安全地到达目标房屋而不被监视发现。 注意，在你潜入房屋时，尚未设立的监视所不会对你造成影响。 输入以如下格式从标准输入给出。 - 第 1 行给出一个整数 $N$，表示要潜入的房屋和监视所的总数。 - 第 2 行到第 $N+1$ 行，每行包含一个字符串 $S_i$ 和两个整数 $X_i$、$Y_i$（$1 \leq i \leq N, 1 \leq X_i, Y_i \leq 10^8$），用空格分隔。 - $S_i$ 为 `TARGET` 或 `MONITOR`，分别表示目标房屋和监视所。 - 所有房屋和监视所的位置都不相同。即对于 $i \neq j$，有 $(X_i, Y_i) \neq (X_j, Y_j)$。 - 潜入房屋的时间和监视所设立的时间按输入顺序给出。 也就是说，在你潜入某个房屋时，已经设立的监视所是指在输入中排在该房屋之前的所有监视所。 - 据点位于原点 $(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 ```

输入的第 1 行包含一个整数 $N$，表示目标房屋和监视所的总数。 接下来的 $N$ 行，每行包含一个字符串 $S_i$（`TARGET` 或 `MONITOR`），以及两个整数 $X_i$、$Y_i$，用空格分隔。

对于每一个目标房屋，按输入顺序输出一行。如果可以安全潜入，输出 `SAFE`，否则输出 `DANGER`。

- 你不能经过任何监视所，也不能穿越任意两个监视所之间的直线。 - 你也不能潜入位于这些直线上的房屋。 - 只有在你潜入房屋时已经设立的监视所才会对你造成影响。 - 据点位于原点 $(0, 0)$。 由 ChatGPT 4.1 翻译