# 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

- 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}/4
≤ 400*10^{6} intersection computations.
Running Dijkstra and computing the graph on the fly
requires K*J^{3}/2 ≤ 80*10^{6}
intersection computations. So use Dijkstra.

## Solution Timing

Each intersection computation requires 6 cross products, or 6BBs.
So Dijkstra requires up to 6*80*10^{6} = 480*10^{6} BBs.
Please send questions or comments to
hc3-coaches@g.harvard.edu.