Solved / AC ratio: 0 ( - % )
Fastest submission : - ( unsolved )
Writer: Astein
결국 도전하신 분들이 아무도 없게 된 버림받은 비운의 문제입니다 :$ 사실 출제하는 입장에서는 알고리즘을 생각하는 것 자체는 쉽기 때문에 그렇게 어렵다고 판단받지 못했던 문제였습니다. 물론 다들 코딩하면서 이러한 판단이 틀렸다고 공감했지만요.
전체적인 접근방법은 아래와 같습니다.

1. 삼각형 A, 삼각형 B를 입력받는다.
2. 삼각형 A 를 포함하는 평면 P를 구한다.
3. 평면 P 위에 삼각형 B가 지나는 자취를 구한다. (이 자취를 B' 라고 합시다.)
4. A와 B' 간에 이루는 도형을 구한다. 간단하게 살을 붙여서 설명을 해 봅시다. 오늘 대회 참가자 분들중에 1번을 못하실 분은 없다고 생각하니 첫 번째 단계의 설명은 패스할께요 :$ 2) "세 점을 지나는 평면의 방정식" 을 구할 차례입니다. 2차원 평면에서 직선의 방정식을 ax + by + c = 0 형태로 나타내는 것처럼, 3차원 공간에서 평면의 방정식은 ax + by + cz + d = 0 꼴로 나타낼 수 있습니다. 그리고 앞의 식에서 (a, b, c) 는 "법선벡터"를 나타냅니다. 좌표가 모두 정수이므로, a, b, c, d는 모두 정수의 형태로 나오게 되고요. 아래는 세 점으로부터 평면의 방정식을 얻어내는 소스코드입니다. ~~~ cpp

void GetPlane(Point A, Point B, Point C)
{
Point v1 = Point(B.x - A.x, B.y - A.y, B.z - A.z);
Point v2 = Point(C.x - A.x, C.y - A.y, C.z - A.z);
// A x B = (a2b3 - a3b2, a3b1 - a1b3, a1b2 - a2b1)
Point v3 = Point(v1.y * v2.z - v1.z * v2.y,
v1.z * v2.x - v1.x * v2.z,
v1.x * v2.y - v1.y * v2.x);
a = v3.x, b = v3.y, c = v3.z;
if (a == 0 && b == 0 && c == 0)
{
// not a plane
assert(false);
}
int g = gcd(a, gcd(b, c));
a /= g, b /= g, c /= g;
d = -(a * A.x + b * A.y + c * A.z);
}

3) 평면이 하나 있다고 하면, 어떤 점의 상태는 크게 3가지로 나눌 수 있습니다. (1) 평면 위쪽에 있는 점, (2) 평면에 포함되는 점 (3) 평면 아래쪽에 있는 점. 또한 이러한 상태는 f(x,y,z) = ax' + by' + cz' + d 를 구하여, 이 부호를 통해 판단할 수 있지요. 가능한 모든 경우를 계산해 보면 10 가지의 상태가 나온다는 사실을 알 수 있습니다. (+++, ++0, ++-, +00, +0-, +--, 000, 00-, 0--, ---)
  삼각형 B와 평면 P가 이루는 자취를 구하는 과정은, 결국 삼각형 B가 평면 P에 몇 번 만나는지로 판단할 수 있습니다. 만약 삼각형 P가 한 번 만난다면 한 점에서 만나는 것이고, 두 번 만나면 SEGMENT를 만들 것이며, 세 번 만난다면 결국 삼각형 B는 평면 P 위에 있다는 결론이 나오지요. 주의해야 할 점은 지금 구한 도형은 "평면 P"에 내린 도형이라는 사실입니다. (우리가 구하고자 하는 것은 삼각형 A와 삼각형 B가 만난 거니까요.)
  삼각형 B의 한 선분과 평면 P가 만나는 교점은, 비례식으로 구할 수 있습니다. 점(x1, y1, z1)과 평면(ax + by + cz + d = 0) 사이의 거리 
D = | ax1 + by1 + cz1 + d | / sqrt(a^2 + b^2 + c^2) 라는 식을 이용하여, 평면에서 각 점까지의 거리를 구하고, 이에 따른 비례식으로 평면 P를 지나는 삼각형 B의 자취를 구합니다. 
~~~ cpp

DPoint GetPointOnPlane(Point a, Point b, Plane p)
{
   double x, y, z; // a.d, b.d 는 점 a, b에서 평면 P 까지의 거리를 의미합니다.
   x = a.x + (0.0 - a.d) / (b.d - a.d) * (b.x - a.x);
   y = a.y + (0.0 - a.d) / (b.d - a.d) * (b.y - a.y);
   z = a.z + (0.0 - a.d) / (b.d - a.d) * (b.z - a.z);
   return DPoint(x, y, z);
}

3번과정까지 진행했으면 "2차원 평면 위에 삼각형 두 개(또는 삼각형과 점 or 선분)가 있을 때, 이루는 도형이 어떤 형태인지를 구하시오" 문제가 됩니다.
4) 그러면 각각의 케이스에 대해 가능한 경우를 살펴보도록 하지요.
4-1) 삼각형과 점 -> EMPTY, POINT
4-2) 삼각형과 선분 -> EMPTY, POINT, SEGMENT
4-3) 삼각형과 삼각형 -> EMPTY, POINT, SEGMENT, OTHERS (넓이를 가지는 도형)
이 됩니다. 그러면 이제 출력 케이스 별로 어떤 체크를 하면 되는지 살펴볼까요?

1. 삼각형과 각 도형이 이루는 교점이 하나도 없고, 포함 관계도 아니라면 "EMPTY" 입니다.
2. "POINT"를 출력하는 경우는 크게 두 가지가 있습니다. 2-1. 삼각형과 점의 경우에서, 점이 삼각형의 내부(혹은 선분 위)에 있을 때 2-2. 삼각형과 선분/삼각형의 경우에서 한 점이 삼각형의 선분 위에 있고, 나머지 두 점은 외부에 있을 때
3. "SEGMENT"를 출력하는 경우도 위에서 했던 것과 같이 나눌 수 있지요. 3-1. 삼각형과 선분의 경우에서. 삼각형의 선분들과 입력받은 선분간의 교점이 2개일 때. 3-2. 삼각형과 삼각형의 경우, "선분끼리 겹칠 때"
4. "OTHERS"의 경우는 1. 2. 3. 모두 해당하지 않는 경우입니다. 그런데 위에서 나눈 4가지 경우의 모두 포함하는 "간단한" 방법이 존재합니다. " Set{CrossP} = (삼각형 A안에 포함되는 B'의 점) U (삼각형 A와 [B'로 만들 수 있는 선분]이 교차하는 점) " 을 구합니다. 만약 이 점이 하나도 없다면 "EMPTY"가 되겠지요. 또한 하나 있는 경우엔 "POINT"가 되고요. 두개 있다면 "SEGMENT"이고 셋 이상일 경우 "OTHERS"로 볼 수 있습니다. 소스코드를 붙여드리고 싶지만...라인이 너무 긴 관계로 ㅜ_ㅜ 생략하도록 하겠습니다 orz...
   [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]