네 점의 거리 조건

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

요약
네 점 사이의 모든 거리가 담긴 4x4 정수 행렬이 주어질 때, 이를 만족하는 서로 다른 네 점이 3차원 공간에 존재하는지 판정합니다.
난이도

보통10점 중 7점

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

문제

네 점 사이의 거리들이 4×4 행렬로 주어진다. 이 거리들을 모두 만족하도록 3차원 유클리드 공간에 서로 다른 네 점을 배치할 수 있는지 판별하라.

입력

입력은 4줄이다. 각 줄에는 4개의 정수가 주어진다. i번째 줄의 j번째 정수는 i번 점과 j번 점 사이의 거리이다.

i번째 줄의 i번째 정수는 항상 0이고, i번째 줄의 j번째 정수와 j번째 줄의 i번째 정수는 같다. i와 j가 서로 다르면 그 값은 10 이하의 자연수이다.

출력

주어진 거리들을 만족하는 네 점이 존재하면 YES, 존재하지 않으면 NO를 출력한다.

힌트

모든 두 점 사이의 거리가 1이면 네 점은 정사면체의 꼭짓점으로 놓을 수 있다.

예제5

  1. 예제 1

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

  2. 예제 2

    입력
    0 1 2 3
1 0 1 2
2 1 0 1
3 2 1 0
    예상 출력
    YES

  3. 예제 3

    입력
    0 1 2 4
1 0 1 2
2 1 0 1
4 2 1 0
    예상 출력
    NO

  4. 예제 4

    입력
    0 6 6 3
6 0 4 5
6 4 0 4
3 5 4 0
    예상 출력
    YES

  5. 예제 5

    입력
    0 6 6 2
6 0 4 5
6 4 0 4
2 5 4 0
    예상 출력
    NO