친구라는 것은, 해변가에서 모래를 한줌 쥐었을 때, 다 흘러내리고 손바닥 안에 남아있는 몇개의 모래알이랑 비슷하다.

계속해서 붙잡지 않으면 모두 흘러내려서 다른 모래알과 구별되지 않을 것이다.

우정이라는 것은, 해변가에서 물을 한손 퍼올렸을 때, 다 흘러내리고 손바닥 안에 남아있는 조금의 물기와 비슷하다.

계속해서 손을 적시지 않으면 모두 말라버려서 손바닥은 결국 메말라 버릴 것이다.

최근에 그렇게 느꼈다.

평면 위에 직선이 하나 있다고 하자. 그 직선은 무한히 먼 곳에서 시작하여 무한히 먼 곳에서 끝난다. 낭만적이지 않은가? 그렇게 길게 이어진 직선은 평면을 두 영역으로 나눈다. 그것이 남과 북이 되었든, 좌와 우가 되었든 문제는 되지 않는다. 평면 위에 있는 모든 점은 따라서 평면에 있는 세개의 부분집합 중 하나에 반드시 포함된다. 왼쪽에 있거나, 오른쪽에 있거나, 또는 직선 위에 있거나. 그중에 없다면 이 점은 평면 위에 있는 점이 아니다.

직선의 방정식은 일반적으로 다음과 같다.

$ax+by+c=0$

이 방정식에다가 어떤 점 (p,q)가 세 집합 중 어디에 있는지 알아보려면?

이렇게 하면 될 것 같다.

$ap+bq+c < 0$ : 왼쪽
$ap+bq+c=0$ : 직선 위

$ap+bq+c >$ 0 : 오른쪽

(여기서, 왼쪽이냐 오른쪽이냐는 전혀 시각적인 이미지가 아니며, 대충 말로 정한 값이다.)

따라서, 어떤 점 두개 (p,q)와 (r,s) 가 있을 때, 직선이 나누는 세 영역 중에서 같은 쪽에 있는지 확인하려면 다음과 같이 하면 된다.

$sgn(ap+bq+c)*sgn(ar+br+c) > 0 $ : 같은쪽

$sgn(ap+bq+c)*sgn(ar+br+c) < 0 $: 다른쪽
$sgn(ap+bq+c)*sgn(ar+br+c) = 0 $: 둘 중 한놈이 직선 위에 있는 놈이다.

그래서, 일단 벡터가 주어졌을 때 직선의 방정식을 한번 써 보자.

벡터가 (x1,y1), (x2,y2) 라고 한다면

$y=\frac{y2-y1}{x2-x1} (x1-x) +y1$

이 수식을 $ax+by+c$ 형태로 바꾸면

$a=y2-y1$

$b=x1-x2$

$c=y1*x2-x1*y2$

이 된다.

이제, 삼각형 내부에 점이 있는지 없는지 판정하는 함수를 만들 준비가 끝났다.

어떤 점이 주어진 삼각형 내부에 있는지 외부에 있는지 판정하는 방법을 드디어 알아냈다. 자세한 증명은 좀 더 명확히 해 보도록 하고 일단 방법부터 설명하도록 한다.

삼각형에 있는 세개의 변 중에 임의의 2개를 고른다. 그리고 그 2개의 변을 양쪽으로 연장해서 평면을 4개로 분할한다. 적당히 그 4개의 분할된 영역을 분면이라고 하고, 1,2,3,4분면이라는 이름을 붙여두자.

[보조정리]

이제, 점이 삼각형 내부에 있다고 가정하자. 그럼 그 점은 반드시 4개의 분면중에 1개에는 들어 있어야 한다. “내부”라고 하였으므로 직선 위에 있는 경우는 없다.

또한, 나머지 한개의 변의 중점을 생각하자. 그 중점 역시 4개의 분면중에 1개에 들어가 있다.

점이 삼각형 내부에 있다면, 나머지 한 변의 중점과 주어진 점은 반드시 같은 분면에 들어간다.

[증명] 일단 생략

[정리]

어떤 점이 삼각형 내부에 있다면, 삼각형에 있는 3개의 변 중에서, 어떤 임의의 2개 변을 선택하더라도 나머지 한 변의 중점과 그 점은 같은 분면 안에 반드시 포함된다. 즉, 2개씩 고르는 작업을 3번 하면 삼각형 내부에 있는지 아닌지를 알아낼 수 있다.

[증명] 어쨌든 일단 생략

직관적으로는 일단 옳다는 결론을 내렸다. 상세한 증명은 그림을 좀 더 그려본 후에 작성해볼 예정이다.

——

더불어, 이 과정은 볼록다각형으로 확장할 수 있다. 볼록다각형은 한 점을 잡고서, 순서대로 점을 두개씩 골라가면 삼각형으로 분할할 수 있기 때문에 각각의 삼각형에 대해서만 판정하면 된다. 물론, 이 경우, 실제로 다각형의 변을 이루는 삼각형의 변과, 다각형 내부에 있는 삼각형의 변 중에서, 만약 그 점이 다각형 내부에 있는 삼각형의 변 위에 있다면 그것은 다각형 내부에 있다는 점을 염두하여 계산할 필요가 있다.

그리고 볼록다각형으로 확장한 다음에는 오목다각형을 포함할 수도 있다. 오목다각형은 볼록다각형 여러개로 잘라낼 수 있기 때문이다.

또한, 다시 이 과정을 다차원으로 확장할 수도 있다. 가령, 3차원의 경우에는 임의의 사면체에 대해서 먼저 증명하면 된다. 이 경우에는 사면체 중 꼭지점 하나를 공유하는 평면 3개를 정하고, 나머지 한 평면의 중점과 필요한 점이 8개의 분할된 공간 중 같은 공간에 속하는지를 판정하면 된다.

4차원에서도 가능할 것 같다. 이 경우에는 사면체 5개로 이루어진 초사면체에서 꼭지점 하나를 공유하는 사면체 4개를 정하고, 나머지 한 사면체의 중점과 필요한 점이 16개의 분할된 공간 중 같은 공간에 속하는지를 판정하면 된다. 물론, 복잡하다. -_-;

고율님 블로그에서 보고 따라해 봤다.

11명 중에 한 사람을 선정하기 위해서 주사위를 굴리기로 했다.

주사위를 유한한 횟수 이내로 굴려 균등한 확률로 11명 중의 한 명을 선정할 수 있는 방법을 서술하시오. (단, 주사위는 정 6면체이다.)

*읽기전에 알아둘 것 :

이 논리는 틀렸습니다!


$(a+b)^2 = a^2+b^2+2ab$

기본 아이디어는 이항전개다.

각 면에 써 있는 숫자를 n이라고 놓고, k번 던진 다음에 나오는 숫자를 계산해 보면

$\left(\sum^6_{i=1}e^n \right)^k$

으로 쓸 수 있고, 이 식에서 각 항마다 있는 계수는 정해진 합에 대해서 그 합이 나오는 경우의 수가 몇개인지 알려준다. 그럼, 적당히 큰 k를 고르고, 그중에 계수가 11을 넘는 합 하나를 가져오자. 합 자체는 얼마가 되든 상관 없다. 그냥 a라고 하자. 그리고 그 계수를 m이라고 하자. m은 이항전개에서 해당 항이 나오는 횟수가 몇번인지 알려준다. 따라서, 이항전개에서 그 항은 11번 이상 나온다.

이 말은 바꿔 말하면, 주사위를 k번 던질 때 전체 가능한 경우의 수 중에서 합이 a가 되는 경우가 m번 있다는 뜻이다. 그럼, 이제 합이 a가 되는 경우 각각을 11명의 사람들에게 배정한다. 경우의 수가 11을 넘어갈 수도 있지만, 나머지는 무시해 버려도 된다. 순서 따져서 각각이 구별 가능하기만 하면 된다.

이제 주사위를 k번 던지는데, 합이 a가 되지 않으면 무시하고, 합이 a가 되면 그렇게 된 경우가 11명의 사람이 배정받게 된 경우 중 어느 것에 해당하는지 따져본다. 아무도 배정받지 않았다면 다시 던진다.

이것이 가능한 이유는 전체 경우의 수 각각이 발생할 확률은 똑같기 때문에, 우리가 원하는 만큼만 골라내고 나머지는 다 버려도 문제가 없다는 것이다.

또한, 합이 a가 나올 확률은 0이 아니므로 반드시 유한한 횟수 안에 끝난다. (물론 계속 합이 a가 나오질 않아서 조금 더 길어질 수는 있으나, 확률이 0이 아니기 때문에 무한히 시행하다보면 실제로 무한까지 가기 전에 유한 횟수 내에 끝나는 것이 보장된다.)