counting points in triangle (1) 썸네일형 리스트형 196. Counting Points in Triangle 이번에는 삼각형 안의 점 개수를 빠르게 세는 테크닉(Counting Points in Triangle)에 대해서 다룬다. 이 테크닉에 붙은 이름은 아직까지는 없는 것으로 알고 있다. 따라서 이 글의 제목도 공식적으로 굳어진 명칭이 아니다. 다음과 같은 문제를 생각해 보자.2차원 좌표평면에 속한 점 n개가 주어진다. 어떤 세 점도 일직선상에 있지 않다. 이제 여기서 세 개의 점을 골라서 삼각형을 만들면 그 삼각형은 다른 점들을 포함할 수도 있다. 이때 점을 0,1,…,n−3개 포함하는 삼각형의 개수를 모두 구하여라.점 n개로 만들 수 있는 서로 다른 삼각형의 수는 $\frac{n(n - 1)(n - 2)}{6} = \frac{1}{6}n^3 - \frac{1}{2}n^2 +.. 이전 1 다음
