양파 껍질

저명한 생물학자 카발(Kabal) 박사는 최근 가장 난치성인 질병까지 치료할 수 있는 액체를 발견했다. 이 액체는 '어니언랜드(Onionland)'라는 나라에서만 자라는 아주 희귀한 양파에서 추출된다. 그러나 어니언랜드의 모든 양파가 실험 대상이 되는 것은 아니다. 껍질(층)의 개수가 홀수인 양파만이 이 기적의 액체를 품고 있다. 참으로 기묘한 발견이다!

그림 1: 어니언랜드의 양파

카발 박사는 양파를 수집하고 분석하기 위해 여러 명의 연구 조교를 고용했다. 아직 발견을 세상에 공개하고 싶지 않았던 그는 조교들에게 "껍질이 홀수 개인 양파를 찾으라"고 말하지 않았다. 대신 각 조교에게 양파를 모으고, 각 껍질(층)의 바깥 경계에서 여러 점을 골라 기록하게 했다. 나중에 이 점들로 양파의 층 구조를 근사적으로 복원할 수 있도록 하기 위해서다. 박사는 다음 단계가 이 점들에 대한 "복잡한 분석"이라고 말했지만, 사실 그가 하는 일은 그 점들로 각 양파의 층 개수를 세어 홀수 개인 것만 고르는 것뿐이다.

그림 2: 한 조교가 수집한 점들

조교가 수집한 점들로 복원한 근사 도형은 원래 양파와 모양이 다를 수 있다. 예를 들어 그림 1의 양파에서 일부 점만 뽑으면 그림 2와 같은 점 집합이 되고, 카발 박사는 이 점들로 원래의 층을 근사해 그림 3과 같은 결과를 얻는다. 근사 방법은 다음과 같다. 모든 점이 정확히 하나의 다각형에만 속할 때까지 볼록 다각형을 겹겹이(중첩되게) 재귀적으로 찾는다. 구체적으로는, 아직 남아 있는 점들의 볼록 껍질(convex hull)을 구해 이를 한 층으로 삼고, 그 껍질 위에 있는 점들을 모두 제거한 뒤, 남은 점들에 대해 같은 과정을 반복한다. 조교들은 이렇게 재귀적으로 근사했을 때의 층 개수가 원래 양파의 층 개수와 같아지도록 점을 고르므로 박사에게는 문제가 없다. 또한 가장 안쪽 층을 포함해 어떤 층이든 근사하려면 점이 최소 3개는 필요하다는 것을 조교들은 알고 있다.

그림 3: 카발 박사의 근사

한 조교가 수집한 점 집합이 주어졌을 때 해당 양파를 실험실로 가져가야 하는지 판정하는 프로그램을 작성하라. 즉, 위 방법으로 층의 개수를 세었을 때 그 개수가 홀수이면 실험실로 가져가야 한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 조교가 수집한 점의 개수를 나타내는 정수 $N$ $(3 \le N \le 2000)$이 주어진다. 이어지는 $N$개의 줄에는 각 점의 좌표를 나타내는 두 정수 $X$, $Y$ $(-2000 \le X, Y \le 2000)$가 주어진다. 입력의 마지막에는 $N = 0$인 테스트 케이스가 오며, 이 경우는 처리하지 않고 입력을 종료한다.

각 테스트 케이스마다 한 줄씩 출력한다. 해당 양파를 실험실로 가져가야 하면(층의 개수가 홀수이면) 다음 문자열을 출력한다.

Take this onion to the lab!

가져가지 않아야 하면(층의 개수가 짝수이면) 다음 문자열을 출력한다.

Do not take this onion to the lab!