Shortest Bike Trip Problem

John wants to ride his bike by the shortest path from point B to point C in the plane. But there are buildings, represented by convex polygons. John cannot ride through a building, but may ride along a side. The buildings do not touch each other, and of course B and C are outside all buildings.

Problem Input

For each test case, first a line containing:

N Bx By Cx Cy

where N is the number of buildings, (Bx,By) is John's starting point, and (Cx,Cy) is John's destination.

This is followed by N lines each of the form

M V1x V1y V2x V2y ... VMx VMy

which list the vertices of a building convex polygon in clockwise order. M is the number of vertices, and the vertices themselves are (V1x,V1y), (V2x,V2y), ..., (VMx,VMy).

All input numbers are integers.

Input is such that the total number of polygon vertices is J < 200.

Problem Output

For each test case, one line containing just the shortest distance with exactly 3 decimal places. Input is such that the shortest path contains at most K < 20 polygon vertices.

Time Limit

5 seconds

Solution

• From geometrical considerations, the solution is a sequence of straight line segments that each end at B or C or a polygon vertex.
• The solution is the length of a shortest path in an undirected graph whose nodes are B and C and the polygon vertices and whose edges are straight lines between nodes that are either polygon sides or are such that their interiors do not intersect any polygon.
• Because the polygons are convex, the interior of any straight line between non-adjacent vertices of a polygon intersects that polygon.
• The interior of a straight line L between a point outside a polygon P and a second point that may or may not be a vertex of P intersects P if and only if it contains a vertex of P or intersects the interior of an edge of P which is not parallel to L.
• Computing the entire undirected graph requires J⁴/4 ≤ 400*10⁶ intersection computations. Running Dijkstra and computing the graph on the fly requires K*J³/2 ≤ 80*10⁶ intersection computations. So use Dijkstra.

Solution Timing

Please send questions or comments to hc3-coaches@g.harvard.edu.