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

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

트라이앵글

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

요약
3차원 공간에 놓인 최대 1000쌍의 서로소 삼각형 고리가 엉켜 있는지 분리 가능한지 판정합니다.
난이도

보통10점 중 7점

유형
기하
정답자
아직 제출이 없습니다

문제

희원이는 생일 선물로 3차원 공간에 놓인 삼각형 두 개를 받았다. 각 삼각형은 아주 가느다란 선분 세 개로만 이루어져 있고, 아무리 세게 눌러도 휘어지지 않는다.

희원이는 삼각형을 하나만 갖고 싶어서 두 삼각형을 서로 멀리 떼어 놓으려고 한다. 삼각형을 옮기는 것도, 돌리는 것도 허용된다. 두 삼각형을 이렇게 떼어 놓을 수 있는지, 아니면 서로 꼬여 있는 상태인지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 TT (1≤T≤10001 \le T \le 1000)가 주어진다. 각 테스트 케이스는 두 줄이다. 첫째 줄에는 첫 번째 삼각형의 꼭짓점을 나타내는 정수 아홉 개 x1x_1, y1y_1, z1z_1, x2x_2, y2y_2, z2z_2, x3x_3, y3y_3, z3z_3이 주어지고, 둘째 줄에는 두 번째 삼각형의 꼭짓점을 나타내는 정수 아홉 개 x1′x'_1, y1′y'_1, z1′z'_1, x2′x'_2, y2′y'_2, z2′z'_2, x3′x'_3, y3′y'_3, z3′z'_3이 주어진다. 좌표는 모두 −1000-1000 이상 10001000 이하이다.

각 삼각형의 세 꼭짓점은 한 직선 위에 있지 않다. 한 삼각형의 변과 다른 삼각형의 변이 만나는 경우는 없고, 두 삼각형을 동시에 포함하는 평면도 없다.

출력

각 테스트 케이스마다 두 삼각형이 꼬여 있으면 YES를, 서로 멀리 떼어 놓을 수 있으면 NO를 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    2
    0 0 0 10 0 0 0 10 0
    1 1 10 1 1 -10 10 10 0
    0 0 0 10 0 0 0 10 0
    11 0 0 0 11 0 11 11 1
    
    예상 출력
    YES
    NO