Problem D

A level is being designed for a new platform game. The locations of the platforms have been chosen. Contrary to popular opinion, platforms can’t float in the air, but need pillars for support. More precisely, each of the two ends of the platform needs to be supported by a pillar standing on the floor or on a different platform.

You will be given the locations of the platforms in a coordinate system as in the left image below. Each platform’s location is determined by its altitude (vertical distance from the ground) and the start and end coordinates in the horizontal direction. Each support pillar is placed half a unit from the end of a platform, as in the right image.

Determine the total length of pillars needed to support all the platforms.

\includegraphics[width=\textwidth ]{platforme.png}
Figure 1: Example level with three platforms. The lowest platform is at altitude $1$, the second lowest at altitude $3$ and the third at altitude $5$.
\includegraphics[width=\textwidth ]{pillars.png}
Figure 2: The total length of pillars needed to support all platforms is $14$.


The first line contains the integer $N$, $1 \le N \le 100$, the number of platforms.

Each of the following $N$ lines contains the position of one platform, three coordinates $Y$, $X_1$ and $X_2$. The first number is the altitude, the other two the horizontal coordinates. All coordinates will be positive integers less than $10\, 000$ satisfying $X_2 > X_1 + 1$ (i.e., the length of each platform will be at least $2$).

The input will be such that no two platforms overlap.


Output the total length of pillars needed to support all the platforms.

Sample Input 1 Sample Output 1
1 5 10
3 1 5
5 3 7
Sample Input 2 Sample Output 2
50 50 90
40 40 80
30 30 70
20 20 60
10 10 50

Please log in to submit a solution to this problem

Log in