algorithms – Number of permutations with satisfactory triangles

We are given $N$ points($N leq 40$), where no combination of three or more points is colinear. The values of $x$ and $y$ are bounded by ($0$,$10^4$). The problem is to find the number of permutations(mod $M$) of the points that satisfy the following properties:

  1. We draw a triangle between the first 3 points of the permutation($p_1$, $p_2$, $p_3$) through the use of line segments
  2. For points $4$ to $N$, we draw exactly 3 line segments from $p_i$ to 3 points $p_j$ ($j < i$), such that none of these line segments intersect with any previous line segments drawn.

I will present 3 test cases that I have generated on my own(and tested via bruteforce).

Test case 1 :


($0$,$0$), ($0$,$4$), ($1$,$1$), ($1$,$2$)

Output = 0 since none of the permutations work.

Test case 2:


($0$,$0$), ($0$,$4$), ($4$,$0$), ($1$,$1$)

Output = 24 since all of the permutations work(4!).

Test case 3 :


($0$,$0$), ($0$,$4$), ($4$,$0$), ($1$,$1$), ($1$,$2$)

Output = 96 since all permutations work unless the first 4 points in the permutation are ($0$,$0$), ($0$,$4$), ($1$,$1$), ($1$,$2$). 5! – 4! = 96

So far I have observed that a valid permutation is one in which you can a draw valid triangle without intersecting the sides of the previous valid triangle. However, I am not sure how to build on this idea to calculate the total number of valid permutations. My solution right now is to bruteforce every permutation and manually check for intersections.