선분과 삼각형

직선 $PQ$의 한쪽에 있는 점의 수를 $n_+$, 반대쪽에 있는 점의 수를 $n_-$라 하자. 세 꼭짓점이 모두 같은 쪽에 있는 삼각형은 선분 $PQ$와 만나지 않으므로 관계 4에 해당한다. 이러한 삼각형은 $\binom{n_+}{3}+\binom{n_-}{3}$개이다.

이제 두 쪽에 모두 꼭짓점이 있는 삼각형을 생각하자. 한쪽에 꼭짓점 $U$가 하나 있고 반대쪽에 두 꼭짓점 $V,W$가 있다고 하자. 직선 $UV$와 직선 $PQ$의 교점 위치를 다음과 같이 분류한다.

• $L$: 교점이 $P$보다 앞에 있다.
• $M$: 교점이 선분 $PQ$의 내부에 있다.
• $R$: 교점이 $Q$보다 뒤에 있다.

$UW$도 같은 방법으로 분류한다. 두 교점은 삼각형과 직선 $PQ$가 만나는 구간의 양 끝점이다. 따라서 두 분류에 따라 삼각형의 관계가 다음과 같이 정해진다.

• $L,R$: 관계 1.
• $L,M$ 또는 $M,R$: 관계 2.
• $M,M$: 관계 3.
• $$ 또는 : 관계 4.

고정한 $U$에 대하여 반대쪽 점 중 분류가 $L,M,R$인 점의 수를 각각 $l_U,m_U,r_U$라 하자. 이 꼭짓점이 한쪽에 혼자 있는 삼각형들이 네 관계에 기여하는 수는 순서대로 다음과 같다.

$$l_Ur_U,\qquad m_U(l_U+r_U),\qquad \binom{m_U}{2},\qquad \binom{l_U}{2}+\binom{r_U}{2}.$$

두 쪽에 모두 꼭짓점이 있는 삼각형에는 한쪽에 혼자 있는 꼭짓점이 유일하므로, 모든 $U$에 대해 이 값을 더하면 각 삼각형을 정확히 한 번 센다.

$l_U,m_U,r_U$를 빠르게 구하자. 좌표계에 아핀 변환을 적용하여 $P=$, 이라 생각해도 된다. 점 에 대해

$$a_X=\frac{x_X}{y_X},\qquad b_X=\frac{x_X-1}{y_X}$$

를 정의한다. 일반 위치 조건에 의해 모든 $y_X$는 $0$이 아니며, 정렬 과정에서 같은 값도 생기지 않는다.

$U$가 직선 $PQ$의 위쪽에 있다면

$$l_U=\#\{V:a_V>a_U\},\qquad r_U=\#\{V:b_V<b_U\}$$

이다. 여기서 $V$는 항상 $U$의 반대쪽 점만을 뜻한다. $U$가 아래쪽에 있다면 부등호 방향이 모두 반대가 된다. 따라서 모든 점을 $a_X$ 순서로 정렬하고 양쪽 점의 누적 개수를 세면 모든 $l_U$를 구할 수 있다. 모든 점을 순서로 다시 정렬하면 모든 를 구할 수 있다. 마지막으로

$$m_U=(U\text{의 반대쪽 점 수})-l_U-r_U$$

이다.

나눗셈과 부동소수점은 필요하지 않다. $\vec d=Q-P$라 하자. 기준점 $B$가 $P$ 또는 일 때 다음 분수를 정렬하면 각각 , 의 순서를 얻는다.

$$\frac{\vec d\cdot(X-B)}{\vec d\times(X-P)}$$

분모가 음수이면 분자와 분모의 부호를 함께 바꾸고, 두 분수는 교차 곱으로 비교한다. 좌표 범위 때문에 교차 곱에는 부호 있는 128비트 정수가 필요하다.

두 번의 정렬이 필요하므로 시간 복잡도는 $O(N\log N)$이고, 공간 복잡도는 $O(N)$이다.

Solution written by GPT5