TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

25.0% (1/4)

Tags

Description

在白宮市,有一種名為騎士的組織負責維護治安。
然而在罪犯層出不窮的情況下,騎士的人手漸漸捉衣見肘。
在這情況下由學生所組成而創立的騎士團就是--「艾斯庫瓦亞」。
艾斯庫瓦亞作為新設立的學生騎士團,實績十分亮眼,破獲了不少案件。
甚至在陰錯陽差之下,擔任了公主的護衛。
為了守護公主的安全,艾斯庫瓦亞拿到了公主預定的行程表。
如果表上有三個預定要去的座標相異地方連成一線的話,因為某些大人的因素,那就是危險的。
現在給你許多公主的預定行程表,請你幫忙判斷每張行程表是否危險。

Input Format

第一行會有一個正整數$t$表示有$t$筆測資。
$t$筆測資,每個測資的第一行會有一個非負整數$n$,表示共有幾個預定的行程點。
接下來$n$行,每行會有兩個整數$x_i$、$y_i$,代表第$i$個行程點的平面座標為$(x_i, y_i)$。

你可以當成$t \leq 10$、$n \leq 5000$、$-10^ 9 \leq x_i, y_i \leq 10^ 9$來做,總之複雜度要求$O(n^ 2)$,因為我好像有亂生一些為了卡掉沒判某些咚咚的測資;然後某些測資時限那麼小是因為是手打出來的唷><。

可以參考:http://codepad.org/8WXW3Uxv

Output Format

對於每筆輸入,如果危險的話請輸出"Dangerous"
反之請輸出"Safe"

Sample Input

2
3
1 1
2 2
3 3
3
1 1
0 0
0 1

Sample Output

Dangerous
Safe

Hints

如果找到題目敘述來源的話可以向出題者要hint喔><
因為這次很多水題(?
而且原本想出的題目在CF上找的到
所以就改成這題也很水的了><

Problem Source

Problem Set and Description by PolarisChiba

Subtasks

For Testdata: 0 ~ 8, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 4000 262144 65536
1 300 65536 65536
2 300 65536 65536
3 1000 65536 65536
4 300 65536 65536
5 300 65536 65536
6 2000 65536 65536
7 300 65536 65536
8 300 65536 65536
9 300 65536 65536
10 1000 65536 65536