Internet Problem Solving Contest

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 (Vx,Vy,0) be the direction of the cables. It is easy to see that Johnny has no reason to leave the plane [x = u*Vy, y = -u*Vx, 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(N2), our solution of the hard task has the time complexity O(N3). 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 :-).