Problem Statement
After that, Manao connected several pairs of points with straight line segments. Namely, he connected points points[i] and points[i+1] for each i between 0 and M-2, where M is the number of elements in points. 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 in which he can complete the traversal.
Definition
- Class:
- PolygonTraversal
- Method:
- count
- Parameters:
- int, int[]
- Returns:
- long
- Method signature:
- long count(int N, int[] points)
- (be sure your method is public)
Constraints
- N will be between 4 and 18, inclusive.
- points will contain between 2 and N-1 elements, inclusive.
- Each element of points will be between 1 and N, inclusive.
- The 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.
18
{1, 7, 18}
Returns: 4374612736
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
14
{6, 14, 13, 1}
Returns: 76864
14
{8, 6, 2, 12, 13}
Returns: 50644
14
{2, 1, 14, 5, 6, 7, 10}
Returns: 276
14
{2, 5, 10}
Returns: 426528
14
{14, 5, 10}
Returns: 1246144
15
{2, 15, 1, 7, 9}
Returns: 95220
15
{8, 1, 4, 15, 11}
Returns: 313496
15
{15, 14, 5, 6}
Returns: 297584
15
{11, 15, 13}
Returns: 2155258
15
{10, 8, 9, 3, 1, 15, 2, 4, 7, 12}
Returns: 16
16
{5, 6, 8, 15, 1}
Returns: 1921728
16
{1, 3, 2, 9, 10}
Returns: 550700
16
{1, 2, 3, 4, 5, 10, 11, 12, 13, 14}
Returns: 44
17
{17, 5}
Returns: 0
17
{16, 17, 5}
Returns: 0
17
{16, 17, 2, 5}
Returns: 2235898
17
{17, 16, 2, 8, 1}
Returns: 13669792
17
{2, 10, 15}
Returns: 2016736816
17
{9, 3, 14}
Returns: 1737906896
17
{10, 3, 14}
Returns: 1915488320
17
{2, 9, 14}
Returns: 2035755456
17
{5, 17, 10, 3, 4}
Returns: 27419344
17
{5, 17, 10, 3, 4, 9, 13, 15}
Returns: 82656
17
{2, 5, 17, 10, 3, 4, 9, 13, 15, 1}
Returns: 1488
17
{2, 5, 17, 10, 3, 4, 9, 13, 15, 1, 14}
Returns: 168
18
{1, 9, 14}
Returns: 27345704640
18
{2, 9, 14}
Returns: 25330052000
18
{17, 9, 2}
Returns: 21968748592
18
{1, 3}
Returns: 0
18
{1, 18, 6}
Returns: 0
18
{18, 9, 1}
Returns: 13109552944
18
{2, 5, 7}
Returns: 480485858
18
{6, 4, 16}
Returns: 1345290076
18
{17, 13, 15, 1}
Returns: 49084416
18
{17, 3, 15, 2}
Returns: 543620160
18
{17, 3, 16, 2}
Returns: 237438720
18
{1, 3, 5, 7, 9}
Returns: 18423198
18
{1, 4, 8, 12, 16}
Returns: 682820640
18
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17}
Returns: 0
18
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 18}
Returns: 1
18
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 17, 18}
Returns: 2
18
{18, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 16}
Returns: 0
18
{18, 2, 3, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 16}
Returns: 2
18
{18, 2, 6, 3, 7, 8, 9, 11, 12, 13, 14, 17, 16}
Returns: 50
18
{18, 2, 6, 3, 7, 8, 9, 10, 11, 12, 13, 14, 17}
Returns: 24
18
{18, 10, 11, 12, 13, 14, 17}
Returns: 235892
18
{1, 6, 12, 18}
Returns: 3314809360
18
{16, 8, 10}
Returns: 17164729212
18
{1, 3, 4, 5, 7, 8, 9, 13, 14, 18}
Returns: 5048
18
{3, 7, 9}
Returns: 1615250194
18
{3, 8, 12}
Returns: 10228234072
18
{1, 2}
Returns: 0
18
{1, 16, 10}
Returns: 4339392736
18
{1, 7, 18}
Returns: 4374612736
5
{4, 3, 1, 5}
Returns: 1
18
{18, 11, 1}
Returns: 7548898656
18
{18, 2, 8}
Returns: 1345290076
18
{1, 7}
Returns: 0
18
{18, 15, 11, 6}
Returns: 2571110656
18
{1, 7, 14}
Returns: 20313615104
18
{5, 11, 18}
Returns: 20313615104
18
{1, 4, 9}
Returns: 3207961952
6
{5, 2, 6}
Returns: 1
18
{1, 5, 9}
Returns: 5195712492
7
{3, 5, 1}
Returns: 2
18
{1, 10, 5}
Returns: 25451110512