7개의 댓글이 있습니다.
-
-
Taeyoon_Lee -
딱봐도 절망적인 문제였습니다.ㅋㅋ 이번 모의고사에는 기하문제가 많았네요. C, E, G..
17년 전 link
-
-
-
Being -
이건 유리수 연산만으로 모든 것을 해결하는 방법입니다.
2. 삼각형 A 를 포함하는 평면 P를 구한다. n(normal vector) = vec(A1->A2) cross vec(A1->A3)
d = n \dot A1
=> n \dot p = d 인 평면 완성3. 평면 P 위에 삼각형 B가 지나는 자취를 구한다. (이 자취를 B' 라고 합시다.)
두 점 s와 e를 지나는 직선의 자취 p = s + t(e - s) for real t
평면과 교점: n \dot p = d
n \dot (s + t(e - s)) = d
n \dot s + t n \dot (e - s) = d
t = (d - n \dot s) / (n \dot (e - s))
=> 교점 구하기 끝4. A와 B' 간에 이루는 도형을 구한다.
2D로 변환하기 위해서 orthogonal basis를 새로 잡습니다. (orthonormal말고..)basis_1 = vec(A1 -> A2)
basis_2 = vec(A1 -> A3) - (vec(A1 -> A3) \dot basis_1) / (norm(basis_1)2) * basis_1 (projection을 잘 생각해보세요. 선형대수학 하면 금방 나오는 부분입니다)
basis_3 = northogonal basis를 모두 구했으니, 점 p를 이 basis로 변환하려면
( p \dot basis_1 / (norm(basis_1)2) , p \dot basis_2 / (norm(basis_2)2) , p \dot basis_3 / (norm(basis_3)2) )
이렇게 해서 z가 상수(d)인 x, y, z를 구했습니다. 그러면 z를 고려하지 않고 x, y 두 변수 위에서(2D) 교차하는지 따지는 것은 polygon clipping을 통해 해결합니다. 즉, 변환된 삼각형 A의 각 변을 따라서 삼각형 B를 잘라내어 새로운 도형을 만듭니다. 이건 2D 직선 교차로 간단하게 해결할 수 있죠. (신경써야 할 부분은 삼각형 B가 항상 'polygon'으로 주어지는 것이 아니라는 것이죠. 어디까지나 평면과 교차하는 부분의 자취 모양을 하고 있으니 직선이거나 점일 수도 있습니다. 그래서 일반적인 polygon-polygon clipping만 해선 위험할 수 있구요)
clipping된 polygon의 꼭지점의 수를 구하면 완성!
0 EMPTY
1 POINT
2 SEGMENT
3~ OTHERS
17년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
astein
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번과정까지 진행했으면 "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...
17년 전