COCI 2007/2008, Croatian Regional

Task PLATFORME

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.

Example level with three platforms. The lowest
platform is at altitude 1, the second lowest at
altitude 3 and the third at altitude 5.

The total length of pillars needed to support
all platforms is 14.

Input

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, X₁ and X₂. The first number is the altitude, the other two the horizontal coordinates. All coordinates will be positive integers less than 10000 satisfying X₂ > X₁+1 (i.e. the length of each platform will be at least 2).

The input will be such that no two platforms overlap.

Output

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

Examples

3
1 5 10
3 1 5
5 3 7

14

5
50 50 90
40 40 80
30 30 70
20 20 60
10 10 50

200

All Submissions
Best Solutions

Point Value: 7
Time Limit: 1.00s
Memory Limit: 32M
Added: Aug 09, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)