아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

저격수

면접 대비

시간 제한2초메모리 제한128 MB

요약
서로 다른 깊이에 놓인 직사각형 창들이 있을 때, X축 위의 한 점에서 발사한 직선이 모든 창을 통과할 수 있는지 판정한다.
난이도

보통10점 중 5점

유형
기하, 이분 탐색, 구간, 수학
정답자
아직 제출이 없습니다

문제

OXYZOXYZ 좌표계를 사용하는 3차원 공간을 생각하자. OXOX 축은 오른쪽, OYOY 축은 위쪽, OZOZ 축은 화면에서 멀어지는 방향을 가리킨다. 이 공간에는 직사각형 창문이 여러 개 있다. 각 창문은 OXYOXY 평면과 평행한 평면 위에 놓여 있으며, 변은 각각 OXOX 축과 OYOY 축에 평행하다. 모든 창문의 깊이는 서로 다르다(각 창문은 서로 다른 좌표 z>0z > 0 을 가진다).

소총을 든 저격수는 OXOX 축 위를 움직이므로, 발사 위치는 항상 y=0y = 0, z=0z = 0 이다. 그는 직선으로 나아가는 총알 한 발을 쏜다. 이 총알이 모든 창문을 통과하게 하고 싶다. 창문의 모서리에 스치기만 해도 통과한 것으로 인정한다.

이러한 발사가 가능한지 판정하여라.

입력

첫째 줄에 창문의 개수 nn (2≤n≤1002 \le n \le 100) 이 주어진다.

다음 nn 개의 줄에는 각 창문을 나타내는 다섯 정수 x1ix_{1i}, y1iy_{1i}, x2ix_{2i}, y2iy_{2i}, ziz_i (0<x1i,y1i,x2i,y2i,zi<10000 < x_{1i}, y_{1i}, x_{2i}, y_{2i}, z_i < 1000) 가 주어진다. (x1i,y1i,zi)(x_{1i}, y_{1i}, z_i) 는 창문의 왼쪽 아래 꼭짓점, (x2i,y2i,zi)(x_{2i}, y_{2i}, z_i) 는 오른쪽 위 꼭짓점이며 x1i<x2ix_{1i} < x_{2i}, y1i<y2iy_{1i} < y_{2i} 이다.

창문은 깊이가 증가하는 순서로 주어진다. 즉 모든 2≤i≤n2 \le i \le n 에 대해 zi>zi−1z_i > z_{i-1} 이다(따라서 모든 깊이는 서로 다르다).

출력

저격수가 직선으로 나아가는 총알 한 발로 모든 nn 개의 창문을 통과(모서리에 스치는 경우 포함)시킬 수 있으면 SOLUTION 을, 그렇지 않으면 UNSOLVABLE 을 출력한다.

예제2

  1. 예제 1

    입력
    3
    1 3 5 5 3
    1 2 5 7 5
    5 2 7 6 6
    
    예상 출력
    SOLUTION
    
  2. 예제 2

    입력
    3
    2 1 5 4 1
    3 5 6 8 2
    4 3 8 6 4
    
    예상 출력
    UNSOLVABLE