사면체 만들기

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

요약
여섯 변의 길이가 주어질 때, 이들을 사면체의 여섯 모서리에 적절히 배치해 부피가 0보다 크도록 만들 수 있는지 판정한다.
난이도

보통10점 중 7점

유형
기하, 정렬, 완전 탐색, 수학
정답자
아직 제출이 없습니다

문제

세 변의 길이가 1, 2, 3인 삼각형은 넓이가 0이 아니게 만들 수 없다는 사실은 잘 알려져 있습니다. 그렇다면 여섯 모서리의 길이가 1, 2, 3, 4, 5, 6인, 부피가 0이 아닌 사면체는 만들 수 있을까요?

주어진 여섯 개의 길이는 사면체의 여섯 모서리에 어떤 방식으로든 배정할 수 있습니다. 어떤 배정으로든 부피가 0보다 큰 사면체를 만들 수 있으면 가능한 것으로 봅니다.

입력

첫째 줄에 이어지는 줄의 개수를 나타내는 정수 nn이 주어집니다 (0<n≤100000 < n \le 10000).

다음 nn개의 줄에는 각각 공백으로 구분된 여섯 개의 양의 정수가 주어지며, 이는 만들고자 하는 사면체의 모서리 길이입니다. 각 모서리의 길이는 10610^6 이하입니다.

출력

각 질의에 대해 한 줄씩, 주어진 길이로 부피가 0이 아닌 사면체를 만들 수 있으면 YES를, 만들 수 없으면 NO를 출력합니다. 총 nn개의 줄을 출력합니다.

예제2

  1. 예제 1

    입력
    1
    1 2 3 4 5 6
    
    예상 출력
    NO
    
  2. 예제 2

    입력
    1
    1 1 1 1 1 1
    
    예상 출력
    YES