0134. Segments

Имя входного файла:	segnemts.in
Имя выходного файла:	segments.out
Ограничение по времени:	500 ms
Ограничение по памяти:	64 megabytes

You are to find the total length of union of n segments located on a horizontal line.

Input file

The first number in the input file is an integer n (1 ≤ n ≤ 5000) representing the number of segments. The rest of file is filled by 2n integers (x₁ y₁ x₂ y₂ …) meaning coordinates of two points confining i segment. All coordinates do not exceed 10⁹ by an absolute value.

Output file

Print only one number – the total length of union of given segments.

Examples:

segnemts.in	segments.out
3 0 5 3 6 7 8	7

Источник: Petrozavodsk Summer 2003. Blitz Kontest, Monday, August 25
Автор: Andrew Lopatin, Nick Durov

Обсудить       Отправить решение



Версия для печати