Simple Hull#12841

Simple Hull (Editorial)

Author: Lucian Bicsi

Solved by:

First to solve: N/A

The first observation is that the area required in the statement somehow translates into the area "enclosed" by the polygonal line; however, this definition might be too informal to help us write a proper algorithm. A more standard way of thinking about this is in terms of planar graphs: in fact, the problem asks us to compute the outer face of the planar graph induced by the segments and their intersections.

Therefore, a straightforward solution is to build the planar graph, and "walk along" the edge of the outer face, in order to compute it. More specifically, after building the graph, you can start from the point with the minimum -coordinate, and minimum -coordinate for ties (this point is surely on the outer face) with the initial direction going up, and then start walking from vertex to vertex. When you are in some vertex, you should decide the next edge by prioritizing [turn left, go straight, turn right, turn around] in this order. This is also popularly known as the "left hand rule" in solving mazes.

Remember, though, that the vertices of the planar graph in question are intersections of segments of the original polygonal line, and there can be \Omega(n^2) many. Therefore, the naive approach is too inefficient to pass the time limit.

However, one may cleverly guess that even though the planar graph is very large, the outer face can't be as big. Indeed, one may prove that the number of vertices and edges on the outer face is almost linear. It can be proven that the size of the outer face is bounded by O(n \alpha (n)), by noticing that the sequence of segments along the face is a Davenport-Schinzel sequence of order 3 (consider the oriented segments p_i \rightarrow p_{i+1} and p_{i+1} \rightarrow p_{i}; consider the walk and enumerate the segment ids that you reach along the path; this enumeration can never contain an alternating subsequence a...b...a...b...a).

Therefore, the faster solution would be to simulate the "walking around" process faster. One may be able to do that in time O(s \log s) using persistent data structures or O(s \log^2 s) using 2D data structures, where is the size of the outer face (s \in O(n \alpha (n))). These data structures should be able to preprocess a list of horizontal/vertical segments and answer queries of form:

"Given a point and a direction up/left/right/down, what is the first segment that intersects the half-line extending in that direction?"

Before initializing the data structures, the overlapping horizontal and vertical segments have to be merged together. This can be done by sorting segments by one of their ends, and then using a stack.

One trick to make the implementation much easier is to consider extending the segments in both ends with a very small value. This has no effect on the answer, but it makes all the vertices of the underlying planar graph look like "+"-shaped intersections (with edges in all four directions), therefore a "left turn" is always available at any intersection. In practice, one achieve this effect without introducing floating point arithmetic by multiplying all coordinates by and extending each segment by one unit to the left and to the right.

The final solution has a complexity of O(n \log(n) \alpha(n)). O(n \log^2(n) \alpha(n)) solutions should also pass, if implemented carefully.