−1000≤x,y≤1000인 좌표평면 위에 임의의 점을 3개 찍으면 삼각형을 만들 수 있다.
다음 두 삼각형을 생각해 보자:
A(−340,495), B(−153,−910), C(835,−947)
X(−175,41), Y(−421,−714), Z(574,−645)
삼각형 ABC에는 원점이 포함되지만, 삼각형 XYZ에는 원점이 포함되지 않는다.
27K 크기의 triangles.txt (우클릭하고 다른 이름으로 저장)에는 1,000개의 임의의 삼각형 좌표가 있다. 원점이 삼각형 안에 엤는 경우는 몇 개인가?
--------------------------------------------------------------------------
해결할 아이디어가 떠오르지 않아 찾아보니 고1 정도의 수학 지식을 필요로하는 문제였다. 벡터를 이용, 삼각형 면적 이용, 도형(삼각형)과 교차하는 점의 갯수, 무게중심좌표 등 해결하는 방법은 몇 가지가 있는데 개념은 알겠는데 실제 어떤 형태로 구현할 것인지는 쉽지 않았다.
이 중 무게중심좌표(Barycentric Coordinate System)를 이용한 해법으로 답을 구했다. 삼각형 세 꼭지점의 좌표를 (x1,y1), (x2, y2), (x3, y3)라 하고, 원점을(xp, yp)라 할 때, 다음과 같이 세 좌표를 계산해서 모두 0보다 크면 삼각형 내부에 있다고 한다.
alpha=((y2-y3)*(xp-x3)+(x3-x2)*(yp-y3)) / ((y2-y3)*(x1-x3)+(x3-x2)*(y1-y3))
beta=((y3-y1)*(xp-x3)+(x1-x3)*(yp-y3)) / ((y2-y3)*(x1-x3)+(x3-x2)*(y1-y3))
gamma=1.0-alpha-beta
왜 그렇게 되는지는 이해 못했지만 위 내용대로 구현하니 답을 구할 수 있었다.
그리고, 왜 이렇게 난이도가 올라갈까 싶었는데, 게임을 할 때 특정 좌표가 도형 내에 있는지 밖에 있는지 판단하는 방법으로 이 코드를 사용할 수 있다고 한다. 좌표가 보호막 내에 있는지 판단하거나, 게임 내의 비행체와 총알의 충돌을 판단하는 등에 사용할 것을 생각하면 이해가 필요한 것 같다.