COCI 2007/2008, Croatian Regional
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.
The first line contains the integer N, 1 ≤ N ≤ 100, the number of platforms.
Each of the following N lines contains the position of one platform, three coordinates Y, X1 and X2. The first number is the altitude, the other two the horizontal coordinates. All coordinates will be positive integers less than 10000 satisfying X2 > X1+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.
3 1 5 10 3 1 5 5 3 7
5 50 50 90 40 40 80 30 30 70 20 20 60 10 10 50
Point Value: 7
Time Limit: 1.00s
Memory Limit: 32M
Added: Aug 09, 2013
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3