## IPSC 2000

## Solution to Problem B – Cake

This problem was not very difficult. Let's draw the lines one after the other.
First line is simple - it divides the plane into 2 parts.
Let's now have n lines in the plane. They divide the plane into m parts.
What happens, when we now add the (n+1)th line ? First n lines will cut
r different intersections on it. These r intersections will divide our line
into r+1 segments. And each of the segments will divide one part of the plane
into two parts. Also r+1 new parts will arise.

So the idea of the algorithm is clear - we will process the lines one after
the other. For each line, we compute its intersections with all the previous
lines, sort them to find out how many different intersections are there
and finally we update the current number of parts.

Sample solution is written in Pascal and should be compiled under a 32-bit
compiler (e.g. FreePascal). It uses rational numbers to avoid
floating-point arithmetics. According to the given restrictions, 64-bit
integers (comp) are precise enough. If you want to compile it under DOS in
Borland Pascal, you should alter the program a bit, because it uses more than
64kb memory.