사면체 Tetrahedron 가 가능한지 여부

사면체(Tetrahedron) 여부 검사

4개의 점이 있고, 각 점들 사이의 거리가 주어져 있다.

이 거리를 가진 4개의 점은 Tetrahedron(사면체) 가 될 수 있는가?

라는 문제이다. (출처 : topcoder)

1. 삼각형 가능 여부 검사

1. 먼저 거리들이 삼각형이 되는지를 검사하자.
////////////////////////////////////////////////////////
for (int i = 0; i < 4; ++i){
    for (int j = 0; j < 4; ++j){
        for (int k = 0; k < 4; ++k){
            if (a[i][j] + a[j][k] < a[i][k])
            return "NO";
        }
    }
}
////////////////////////////////////////////////////////

2. 사면체 가능 여부 검사

2. 그리고 이제 그런 삼각형들이 모여서 과연 사면체(Tetrahedron)을 만들수 있는 지 보자.
////////////////////////////////////////////////////////

double x0 = 0;
double y0 = 0;
double x1 = a[0][1];
double y1 = 0;
double x2 = (a[0][2] * a[0][2] - a[1][2] * a[1][2] + x1 * x1) / (2 * x1);
double y2 = sqrt(a[0][2] * a[0][2] - x2 * x2);
double x3 = (a[0][3] * a[0][3] - a[1][3] * a[1][3] + x1 * x1) / (2 * x1);
double y3 = sqrt(a[0][3] * a[0][3] - x3 * x3);
if (hypot(x2 - x3, y2 - y3) - EPS < a[2][3] && hypot(x2 - x3, y2 + y3) + EPS > a[2][3])
    return "YES";
else
    return "NO";

////////////////////////////////////////////////////////

a[0][1] : 점 '0' 과 점 '1' 사이의 거리를 뜻한다.

2.1 거리에 근거한 4개점의 좌표 구하기

일단 거리에 근거한 점을 구해보자. 사실 정확히 따지면 z 좌표가 필요하다.
하지만 사면체(Tetrahedron)인지 여부만을 판단할 것이므로 굳이 없어도 된다.

x0, y0, 을 (0, 0)으로 가정하고,

x1, y1 은 (a[0][1], 0) 이라고 가정하자.

그리고 x2, y2 를 구해보자.

x2 -------------------------------------------
(a[0][2])²  = (x2)² + (y2)²

(a[1][2])2  = (y2)2 + (x2 – x1)2 
(a[0][1])2  = (x1)2

(a[0][2])2 - (a[1][2])2 
= (x2)2 + (y2)2 - (y2)2 - (x2 – x1)2 
= 2(x2 • x1)

{ (a[0][2])2 - (a[1][2])2 } / 2 • (a[0][1])
= 2(x2 • x1) / 2 • (x1) 
= x2
----------------------------------------------

y2 -------------------------------------------




----------------------------------------------

x3, y3 도 같은 방식으로 구한다.
그러면 좌표는 2차원 평면에 4개의 점이 있게 된다.



2.2  a[2][3] 거리의 가능여부 검사

여기서 궁금증이 생긴다.
주어진 거리를 가진 사면체가 가능한지를 확인하는 것이라면,
 a[0][1], a[0][2], a[0][3]
 a[1][2], a[1][3]
 a[2][3]
이 만족하는 지를 봐야 한다.
여기서 우리는 (x0,y0), (x1,y1), (x2,y2), (x3,y3) 를 
 a[0][1], a[0][2], a[0][3]
 a[1][2], a[1][3]
를 이용해 구했다.
그렇기 때문에 (x0,y0), (x1,y1), (x2,y2), (x3,y3) 는
 a[0][1], a[0][2], a[0][3]
 a[1][2], a[1][3]
를 당연히 만족한다.

하지만 
 a[2][3]
는 만족하는지 알 수 없다. 그렇기 때문에 a[2][3]에 대한 검증이 필요하다.

여기서 알아야 할 것이 있다. 사면체에서 3점의 좌표는 2차원 평면에서 가능하다.
하지만 1개의 점은 다른 2차원 평면에 있어야 한다.
즉 다른 z 값을 갖게 된다.

자, 이제 상상력이 필요하다. 밑에 숫자가 점이다.

저기 삼각형(0,3,1) 을 보자.
저 삼각형의 모양을 유지한채로 x축(선분 0,1)을 중심으로 움직여 보자.
삼각형을 오른쪽 3에서 왼쪽 3으로 회전시킨다면,
2, 3 사이의 거리는 점점 길어진다.

즉 a[2][3] (2와 3의 거리) 는
(x2, y2)와 (x3, y3) 이 같은 z 상에 위치할 때 ,
가장 짧은 길이와, 가장 긴 길이가 가능하다.(빨간 선을 참고하자.)

그래서 "가장 긴 길이" 와 "가장 짧은 길이" 사이에 a[2][3]이 들어간다면,

사면체가 가능하다고 볼 수 있다. 그러므로 밑의 식이 가능한 것이다.

if (hypot(x2 - x3, y2 - y3) - EPS < a[2][3]
    && hypot(x2 - x3, y2 -(-y3) + EPS > a[2][3])