 HC3 Selection Theory Contest Sample Problem

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.

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 J4/4 ≤ 400*106 intersection computations. Running Dijkstra and computing the graph on the fly requires K*J3/2 ≤ 80*106 intersection computations. So use Dijkstra.

Solution Timing

Each intersection computation requires 6 cross products, or 6BBs. So Dijkstra requires up to 6*80*106 = 480*106 BBs.