4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Can you tell us the context where you encountered this task? Can you credit the original source? (i.e., link to it) $\endgroup$ – D.W. Apr 5 at 7:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.