PICTURES deals with a geometric problem in order to find the perimeter of a set of rectangular pictures.

The solution is unique, although one can use distinct approaches to achieve it. For this reason, different implementations may run with very different execution times depending on the kind of input files.

The problem can also be solved for one or several particular cases only. Since some of these cases seem to be very straightforward, the contestants don't need to devise a complete solution to pass some of the tests that were previously planned.

We expect the contestants consider two basic approaches to the solution: scan-line and perimeter summation algorithms.

Scan-line

The main idea of the scan-line algorithm is that any horizontal line may intersect some of the pictures: the intersections are easily known if y-coordinates are compared.

Therefore, by traversing the line from left to right, a counter can be implemented such as it will be incremented every time a left edge of any picture is intersected and decremented when the same happens with a right edge. The perimeter value is then incremented whenever the counter changes from ~0~ to another value or becomes ~0~. Only those transitions contribute to the perimeter, but the final solution still needs the same technique to be applied to the pictures with the vertical lines as well. A practical way to manage this case is by swapping the x- and y-coordinates and applying the same horizontal scanning once more.

Perimeter summation

In the second approach, the perimeter results from the sum of the perimeter of each picture. Not only the initial pictures – read from the input file – are to be considered in this process. As a matter of fact, the intersections between each pair of pictures must be treated as new pictures and the corresponding perimeter subtracted from the global perimeter evaluated so far. This way, for ~N~ input pictures, one can expect up to ~2^N-1~ pictures as the total number. Fortunately, a real layout of pictures on a wall normally doesn't generate such a large number of geometric entities!

Complexity

As it can be seen at this moment, the scan-line algorithm depends linearly on the number of pictures in the input file and also on the range of coordinates, while the performance of the perimeter sum depends exponentially on the number of pictures and their overlapping degree.