A Segment and Triangles

Let $n_+$ and $n_-$ be the numbers of points on the two sides of the line $PQ$. If all three vertices of a triangle lie on the same side, the triangle is disjoint from $PQ$ and has Type 4. There are $\binom{n_+}{3}+\binom{n_-}{3}$ such triangles.

Now consider a triangle with vertices on both sides. Let $U$ be its only vertex on one side, and let $V,W$ be the two vertices on the other side. Classify the position where the line $UV$ intersects the line $PQ$ as follows.

• $L$: the intersection is before $P$.
• $M$: the intersection is in the interior of the segment $PQ$.
• $R$: the intersection is after $Q$.

Classify $UW$ in the same way. These two intersections are the endpoints of the interval where the triangle meets the line $PQ$. Consequently, the pair of labels determines the type of the triangle.

• $L,R$: Type 1.
• $L,M$ or $M,R$: Type 2.
• $M,M$: Type 3.
• $$ or : Type 4.

For a fixed $U$, let $l_U,m_U,r_U$ be the numbers of points on the opposite side with labels , respectively. The triangles for which is the unique vertex on its side contribute the following amounts to the four types:

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

Every triangle having vertices on both sides has a unique vertex on the minority side. Therefore, summing these values over all $U$ counts every such triangle exactly once.

It remains to compute $l_U,m_U,r_U$ efficiently. Apply an affine change of coordinates and regard $$ and . For a point , define

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

The general-position condition guarantees that every $y_X$ is nonzero and that no ties occur in either ordering.

If $U$ is above the line $PQ$, then

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

where $V$ ranges only over points on the side opposite to $U$. If $U$ is below the line, both inequalities are reversed. Thus, sorting all points by $a_X$ and scanning prefix counts for the two sides gives every $l_U$. A second sort by gives every . Finally,

$$m_U=(\text{number of points opposite to }U)-l_U-r_U.$$

No division or floating-point arithmetic is needed. Let $\vec d=Q-P$. For a base point $B$ equal to $P$ or , sorting the following fraction gives the order of or , respectively:

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

If the denominator is negative, negate both the numerator and denominator. Compare two fractions by cross multiplication. Signed 128-bit integers are required for these products under the coordinate bounds.

The two sorts take $O(N\log N)$ time, and the algorithm uses $O(N)$ memory.

Solution written by GPT5