프로젝트 오일러 102번

Three distinct points are plotted at random on a Cartesian plane, for which \(-1000 \le x, \; y \le 1000\), such that a triangle is formed.

Consider the following two triangles: \[ {\rm A}(-340,\; 495), \; {\rm B}(-153, \;-910), \; {\rm C}(835, \; -947)\] \[ {\rm X} (-175, \; 41),\; {\rm Y}(-421, \; -714),\; {\rm Z}(574, \; -645)\]

It can be verified that triangle \(\rm ABC\) contains the origin, whereas triangle \(\rm XYZ\) does not.

Using trianlges.txt, a 27K text file containing the coordinates of one thousand "random" triangles, find the number of triangles for which the interior contains the origin.

NOTE: The first two examples in the file represent the triangles in the example given above.

---

좌표평면위에 세 개의 서로 다른 점들로 이루어진 삼각형이 있다. 각 점의 \(x\) 좌표와 \(y\) 좌표는 모두 \(-1000 \le x, \;y \le 1000\) 의 범위에 있다.

다음의 두 삼각형을 보자.

\[ {\rm A}(-340,\; 495), \; {\rm B}(-153, \;-910), \; {\rm C}(835, \; -947)\] \[ {\rm X} (-175, \; 41),\; {\rm Y}(-421, \; -714),\; {\rm Z}(574, \; -645)\] 

삼각형 \(\rm ABC\) 의 경우 삼각형 내부에 원점을 포함하고 있는 반면, 삼각형 \(\rm XYZ\) 의 경우는 삼각형 내부에 원점을 포함하고 있지 않다.

triangles.txt 에는 1000 개의 서로 다른 삼각형을 만들 수 있는 세 꼭짓점들의 좌표가 들어 있다. 이 1000개의 삼각형 중, 내부에 원점을 포함하고 있는 삼각형의 개수를 구하시오. 

좌표평면 위의 세 점이 주어져 있을 때, 이 세 점으로 이루어지는 삼각형이 원점을 내부에 포함하고 있는지를 판단하는 문제다. 처음에 이 문제를 고1 수학에 등장하는 "부등식의 영역"을 이용하여 풀려고 하였으나, 이게 이론은 쉬워도 구현이 어렵다는 문제점을 알게 되었다. 그래서 다른 방법을 고민하다가 하나의 아이디어를 얻었다. 바로 삼각형의 넓이를 이용하는 것이다.  

위 그림처럼 원점이 삼각형의 내부에 있다면 다음의 관계가 성립하게 된다.

\[\rm \triangle ABC = \triangle OAB + \triangle OBC + \triangle OCA\]

즉, 전체 삼각형의 넓이는 원점 \(\rm O\) 에 의해서 나뉘어진 세 삼각형 \(\rm \triangle OAB, \; \triangle OBC, \; \triangle OCA\) 의 넓이의 합과 같다는 것이다. 만약 원점이 삼각형의 외부에 놓이게 된다면 위와 같은 관계가 성립하지 않게 되리라는 것은 간단히 그림을 그려서 확인할 수 있을 것이다.

그렇다면 세 점의 좌표가 주어졌을 때, 삼각형의 넓이를 구하는 방법을 알아야 하는데, 이것 역시 고등학교 수학 교과과정에 등장하는 내용이다. 세 점이 \({\rm A}(x_1, \; y_1), \; {\rm B}(x_2, \; y_2),\; {\rm C}(x_3, \; y_3)\) 로 주어졌다면 삼각형 \(\rm ABC\) 의 넓이는 다음과 같이 구할 수 있다. 

\[\triangle {\rm ABC} = \dfrac{1}{2} \left | x_1 y_2+x_2y_3+x_3y_1-x_2y_1-x_3y_2-x_1y_3 \right | \]

이 내용을 자세하게 확인하고 싶으면 '삼각형의 넓이' 라는 게시물을 확인하면 될 것이다. (고1 수준에서 이해할 수 있는 증명을 보여주고 있다. 만약 벡터에 대한 개념이 있다면 벡터를 이용해서도 증명할 수 있다.)

아마 이 정도 힌트라면 충분히 이 문제를 해결할 수 있으리라 생각된다.