## IPSC 2004

## Solution to Problem F – Fat Rat

This was probably the most difficult task. Solving it in general is really
hard. Fortunately, some tricks could simplify things a bit.

First of all, we modify each problem instance in the following way:
We increase diameters of all cables and decrease the diameter of the pipe
by the diameter of Johnny. Next, we set the diameter of Johnny to zero.
Obviously, the solutions of the modified problem and the original problem
are the same.

In both tasks, all cables are placed orthogonal to z-axis. Furthermore, in
the easy task all cables are parallel to each other.
Let **(V**_{x},V_{y},0) be the
direction of the cables. It is easy to see that Johnny has no reason to
leave the plane [**x = u*V**_{y}, **y = -u*V**_{x}, **z = u**], i.e. the plane orthogonal to
cables and containing z-axis. Hence it is sufficient to solve
the two-dimensional variant of the problem.

In the two-dimensional variant, cables are circles and pipe is an infinitely
tall rectangle. We build an undirected graph, whose vertices are the
cables, left side of the pipe and right side of the pipe. Two vertices are
connected by an edge if and only if Johnny cannot pass between them. Now
all we need to do is to find out whether there exists a path between left
and right side of the pipe. If it does, Johnny cannot pass through the
pipe, otherwise he can.

In the difficult task, cables are orthogonal to z-axis, but they are not
parallel to each other. But fortunately ( :-) ) they are placed in
``layers''. The axes of all cables in one particular layer have the same
z-coordinate. And each two layers are distant enough so they do not
interfere. Hence Johnny can pass through the pipe if and only if he can
pass through each layer.

How to test whether Johnny can pass through one particular layer? If we look
through the pipe in the direction parallel to z-axis, pipe is seen as a
circle and cables are seen as infinitely tall rectangles. We need to
compute whether there exists some point in the circle that is outside all
rectangles. To do this, for each two rectangles we compute their intersections
and for each rectangle we compute its intersections with the circle. If some
of the intersections is both outside of all rectangles (point on the edge is considered outside)
and inside the circle, Johnny can pass, otherwise he cannot. Well, except for
one special case – if no cable crossing the pipe in this layer.

Our solution of the easy task has the time complexity **O(N**^{2}),
our solution of the hard task has the time complexity **O(N**^{3}).
Here **N** is the number of cables in the pipe.
There are faster solutions (i.e. the time complexities are not optimal),
but writing a faster solution would be a waste of time :-).