Subtask 1

Subtask 1 can be solved by hand. If ~N = 2~, we can draw one segment between the two points. If ~N = 3~, we can draw all three segments between the points, forming a triangle.

If ~N = 4~, there are two cases. If the four points form a convex quadrilateral, we can draw the four edges of this quadrilateral. Otherwise, some point ~p~ lies inside the triangle formed by the other three points, and we can draw three segments connecting ~p~ to the other points.

These cases can be distinguished using a ccw orientation predicate and some careful casework.

Subtask 2

Subtask 2 can be solved using a recursive backtracking brute force. The number of ways to draw segments can be bounded above by ~2^{\frac{N(N-1)}{2}} \le 2^{28}~, and the number of ways without intersecting segments is significantly lower. An implementation that prunes as soon as two segments intersect should easily pass.

Subtask 3

Subtask 3 can be solved by drawing the edges of the polygon. These edges can be found in many ways (e.g., by sorting points by angle with respect to an arbitrary point, or by using a general convex hull algorithm).

Subtask 4

Subtask 4 is the main non-trivial subtask. To motivate the construction, it may help to look at several small examples, such as the following (possibly with the help of a brute-force solver like the one from subtask 2):

11
18 9
-9 -18
-18 9
0 0
20 4
-20 4
-3 20
9 -18
14 -14
-14 -14
3 20

      

The vertices on the outer polygon appear to be partitioned into several consecutive groups, which are attached like "petals" to the inner point, say ~p~. These petals should be constructed so that the robot always traverses entire petals at once, and when the robot switches to a different petal, it should always start at the "leftmost" segment of the petal (joining ~p~ to a vertex on the outer polygon).

To enforce these properties, we can ensure that the reflections of the petals over ~p~ land in empty areas. These ideas motivate the following construction:

• Consider the segments formed between ~p~ and the points on the outer polygon, along with their extensions past ~p~. Sort them by angle with respect to ~p~, and consider the ranges of segments not separated by an extension. Use these ranges to form the petals.

Subtask 5

The subtask 4 solution generalizes recursively to subtask 5. Instead of stopping at "petals" in the shape of a single segment or a convex polygon, the "petals" now form smaller subproblems. The full construction is as follows:

• Recursively construct the graph. If there are only two points, draw the edge between them. If the points form a convex polygon, draw the edges of that polygon. Otherwise, choose an arbitrary point ~p~ that is not on the convex hull. Consider the segments formed between ~p~ and the other points, along with their extensions past ~p~. Sort them by angle with respect to ~p~, and consider the ranges of segments not separated by an extension. If ~S_1,\dots,S_k~ are these sets of points, then recursively construct a solution for the sets ~S_1 \cup \{p\},S_2 \cup \{p\},\dots,S_k \cup \{p\}~.

There are at most ~N~ recursive calls, each requiring ~\mathcal{O}(N \log N)~ time to find a convex hull and sort points by angle, so the time complexity is ~\mathcal{O}(N^2 \log N)~.

Remark 1. The graph of segments constructed this way always forms a cactus graph. It uses at most ~\frac{3(N-1)}{2}~ edges.

Remark 2. The time complexity of the algorithm can reach ~\Omega(N^2 \log N)~ in the worst case: take a regular polygon with ~\frac{N}{2}~ vertices and add ~\frac{N}{2}~ more points close to the midpoints of the sides, but inside the polygon. No matter which ~p~ is chosen (in particular, randomization does not help), each level of recursion will reduce the problem size by only a constant.