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.

Time Limit

5 seconds


Solution Timing

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

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