Tin Cutter II |
In a Tin Cutting factory there is a machine for cutting parts from tin plates. It has an extraordinarily sharp knife able to make horizontal or vertical segment cuts in the tin plates. Each cutting process consists of a sequence of such cuts. Each segment cut is given by its endpoints that are always located inside the tin plate. During the cutting process some parts of tin plate can fall out and so some holes in the plate can emerge.
Factory management needs to predict the length of visible border lines at the end of the given sequence of cuts. Write a program that answers this question.
Here are four examples:
The first row in the picture are four cuttings and the second row contains their corresponding resulting plates. Each gray area is a separate hole, and thick lines are visible border lines after cutting. There are 2, 2, 1, 1 holes respectively (from left to right), and the length of visible border lines are 8, 26, 12, 20 respectively.
4 6 0 0 1 0 1 0 1 2 1 2 2 2 2 2 2 1 2 1 0 1 0 1 0 0 9 0 0 4 0 4 0 4 4 4 4 0 4 0 4 0 0 6 1 8 1 8 1 8 3 8 3 6 3 6 3 6 1 2 2 7 2 8 0 1 3 1 3 1 3 2 3 2 0 2 0 2 0 1 1 0 2 0 2 0 2 3 2 3 1 3 1 3 1 0 8 0 1 4 1 4 1 4 4 4 4 0 4 0 4 0 1 3 0 6 0 6 0 6 2 6 2 3 2 3 2 3 0
8 26 12 20