# 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 :

$$N=4$$

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

Output = 0 since none of the permutations work.

Test case 2:

$$N=4$$

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

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

Test case 3 :

$$N=5$$

($$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.

Posted on