Internet Problem Solving Contest

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.