Number of triangulations P45584


Statement
 

pdf   zip

html

You are given a polygon with n sides without self-intersections. In how many ways can you triangulate it?

Input

Input consists of several cases with only integer numbers. Each case begins with n, followed by the n coordinates x y of the vertices given in counterclockwise order. Assume 3 ≤ n ≤ 200 and | x |, | y | ≤ 106. The given polygons are such that no triangulation contains a degenerate triangle.

Output

For every case, print the number of triangulations modulo 109 + 7.

Public test cases
  • Input

    4
    0 0  1 0  1 1  0 1
    4
    0 0  100000 100000
    200000 0  100000 200000
    7
    2 0  3 2  2 4  0 5  -2 4  -3 2  -2 0
    8
    1 1  0 3  -1 1  -3 0
    -1 -1  0 -3  1 -1  3 0
    8
    0 0  10 0  10 10  0 10
    1 9  9 9  9 1  1 1
    

    Output

    2
    1
    42
    30
    8
    
  • Information
    Author
    Gerard Orriols
    Language
    English
    Official solutions
    C++
    User solutions
    C++