Problem Statement
After that, Manao connected several pairs of points with straight line segments. Let M be the number of elements in points. Manao connected points points[i] and points[i+1] for each i between 0 and M-2. Note that all numbers in points are distinct.
Manao took a look at what he had drawn and decided to continue his traversal by adding every remaining point of the polygon to it and then returning to point points[0]. In other words, Manao is going to connect point points[M-1] with some point tail[0] which is not in points, then connect tail[0] with some point tail[1] which is neither in points nor in tail, and so on. In the end, he will connect point tail[N-M-1] with point points[0], thus completing the traversal.
Manao is really fond of intersections, so he wants to continue the traversal in such a way that every new line segment he draws intersects with at least one of the previously drawn line segments. (Note that the set of previously drawn segments includes not only the original set of segments, but also the new segments drawn before the current one.) Count and return the number of ways for him to complete the traversal.
Definition
- Class:
- PolygonTraversal2
- Method:
- count
- Parameters:
- int, int[]
- Returns:
- int
- Method signature:
- int count(int N, int[] points)
- (be sure your method is public)
Constraints
- N will be between 4 and 13, inclusive.
- points will contain between 2 and N-1 elements, inclusive.
- Each element of points will be between 1 and N, inclusive.
- All elements of points will be distinct.
Examples
5
{1, 3, 5}
Returns: 1
The only way for Manao to complete the traversal is:
6
{1, 4, 2}
Returns: 1
The only way to complete the traversal is to visit vertices {6, 3, 5, 1}, in order. Note that the segment 5-1 does not intersect the original two segments (1-4 and 4-2), but it does intersect segments 2-6 and 6-3 which were both added before 5-1.
7
{2, 4, 7}
Returns: 2
The two possible tails are: 3-5-1-6-2 3-6-1-5-2
7
{1, 2, 3, 4, 6, 5}
Returns: 0
Manao needs to connect points 5 and 7 and then connect points 7 and 1. Obviously, segment 1-7 will not intersect with any other segment.
11
{1, 5, 10}
Returns: 1412
4
{1, 3}
Returns: 0
4
{1, 2, 3}
Returns: 0
4
{1, 2, 4}
Returns: 0
5
{1, 4}
Returns: 0
5
{1, 5, 3, 2}
Returns: 1
5
{5, 2, 1}
Returns: 0
5
{4, 1, 5, 2}
Returns: 0
6
{2, 4, 6}
Returns: 1
6
{6, 5, 2}
Returns: 0
6
{6, 3, 1}
Returns: 1
6
{3, 4, 2, 6, 5}
Returns: 1
7
{7, 1, 5, 3}
Returns: 2
7
{2, 5, 1}
Returns: 4
7
{1, 2, 6, 7, 3}
Returns: 0
7
{1, 2, 4, 7, 6}
Returns: 1
8
{3, 5, 7, 1}
Returns: 6
8
{1, 2, 4, 8}
Returns: 0
8
{2, 4, 1, 7}
Returns: 2
8
{1, 7, 3}
Returns: 2
8
{2, 5, 8, 1, 7, 3}
Returns: 1
9
{1, 4, 7}
Returns: 56
9
{4, 7, 2}
Returns: 38
9
{1, 5, 9, 2, 6}
Returns: 4
10
{1, 9, 4}
Returns: 52
10
{1, 5, 8}
Returns: 400
10
{1, 5, 8, 10}
Returns: 116
11
{5, 6, 8, 1}
Returns: 86
11
{1, 3, 11, 6}
Returns: 56
11
{10, 3, 7, 1, 11}
Returns: 146
11
{11, 10, 2, 3, 7, 1}
Returns: 20
12
{6, 11, 12}
Returns: 6100
12
{6, 11, 12, 1}
Returns: 1140
12
{6, 11, 12, 1, 3}
Returns: 326
12
{5, 7, 1, 9, 10}
Returns: 796
12
{10, 11, 12, 3, 8, 1, 5, 2}
Returns: 10
13
{1, 2, 3, 4, 5, 6, 7, 8, 9, 12}
Returns: 0
13
{1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 10, 13}
Returns: 1
13
{1, 2, 13, 4, 5, 11, 7, 8, 9, 12}
Returns: 6
13
{6, 2, 12}
Returns: 70168
13
{4, 1}
Returns: 0
13
{13, 1}
Returns: 0
13
{13, 1, 5}
Returns: 0
13
{8, 6, 1, 5, 13}
Returns: 1576
13
{1, 7, 11}
Returns: 154108
13
{1, 6, 11}
Returns: 133032
13
{7, 3, 12}
Returns: 101044
11
{1, 5, 10 }
Returns: 1412
13
{7, 8, 9, 1, 2, 3, 4, 5, 10, 11, 12, 6 }
Returns: 1
11
{1, 3 }
Returns: 0
13
{12, 3, 4, 5, 6, 7, 8 }
Returns: 34
13
{1, 5, 10 }
Returns: 103784
13
{3, 7, 10 }
Returns: 70168
5
{2, 4 }
Returns: 0