PolygonTraversal2
SRM 574 · 2012-12-13 · by gojira_tc
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.
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.
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
Submissions are judged against all 58 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PolygonTraversal2 with a public method int count(int N, vector<int> points) · 58 test cases · 2 s / 256 MB per case