딴짓을 하지 말자

정올 수업 시간에 KRUNKER나 애벌레 게임 등을 하다 걸린 몇몇 학생들이 운동장에서 기합을 받고 있다.

N명의 학생들은 2차원 좌표평면으로 표현될 수 있는 운동장에 한 명당 하나의 트랙을 받는다. 트랙은 x축에 평행하거나 y축에 평행한 선분 형태이다.

선생님이 호각을 불면, 기합 받는 학생들은 다음 호각 소리가 들릴 때까지 선분의 한쪽 끝에서 다른 쪽 끝을 향해 전력으로 뛰고, 다시 시작점으로 돌아오고 …를 무한정 반복한다.

거기다가 학생들은 그냥 뛰어다니는 것이 아니라 "딴짓을 하지 말자!"를 반복적으로 외치면서 뛰어다녀야 한다!

기합을 받다가 학생들이 서로 부딪혀 다치면 안되기 때문에, 트랙을 잘 짜는 것이 중요하다.

그림 1과 같이 4개의 트랙 (s₁,s₂,s₃,s₄)이 있는 경우는 트랙 s3을 도는 학생과 s4를 도는 학생이 부딫힐 수 있어서 위험한 경우이며,

그림 2와 같이 3개의 트랙(s₁,s₂,s₃)가 있는 경우는 안전한 경우이다.

그림 1

그림 2

트랙의 정보가 주어졌을 때, 안전 여부를 판단하는 프로그램을 작성하라.

(모든 학생들의 달리는 속도는 모두 다르다고 가정한다.)

입력

가장 첫 줄에 테스트케이스의 수 T가 주어진다. (1≤T≤10)

각 테스트케이스별로, 첫 줄에는 학생의 수인 N(2≤N≤1,000)이 주어진다.

다음 N줄에 걸쳐서, x_1, y_1, x_2, y_2가 각각 공백을 사이에 두고 주어진다.

이는 해당 트랙을 나타내는 선분이 (x_1, y_1)부터 (x_2, y_2)까지임을 뜻한다.

모든 트랙에 있어서 x_1 = x_2 또는 y_1 = y_2임을 만족하고, x_1 = x_2이면서 동시에 y_1 = y_2인 트랙은 없음을 만족한다.

모든 좌표값 x_1, y_1, x_2, y_2는 1이상 1,000,000,000(10억)이하의 정수이다.

출력

테스트케이스별로, 안전한 경우 SAFE, 위험한 경우 DANGEROUS를 출력한다.

(미리 말하지만 모든 테스트케이스의 출력결과가 모두 SAFE이거나 모두 DANGEROUS인 입력데이터는 존재하지 않으므로, 그러한 코드를 제출할시에는 당연히 0점이다.)

[추가제약조건]

위에 주어진 입력 형식에서 모두 잘 작동하는 프로그램을 작성한다면 100점을 받을 수 있다.

부분문제

번호	점수	조건
#1	점	N = 2인 경우에만 작동하는 프로그램을 작성하면 10점을 받을 수 있다.
#2	점	모든 트랙이 세로선(즉, 모든 선분에 있어서 x₁= x₂)인 경우에 작동하는 프로그램을 작성하면 35점을 받을 수 있다.
#3	점	N ≤ 100이고, 모든 좌표값 x₁, y₁, x₂, y₂의 값이 100이하의 정수인 경우에 작동하는 프로그램을 작성하면 35점을 받을 수 있다.

예제

태그

출처

JUNGOL - ohjtgood

딴짓을 하지 말자 1s 128MB