Большие скачки

시간 제한2초메모리 제한1024 MB

요약

직선과 N개의 원이 주어질 때, 하나 이상의 원이 덮는 직선 부분의 총 길이를 구한다.

난이도: 보통10점 중 6점
유형: 기하, 정렬, 구간, 수학
정답자: 아직 제출이 없습니다

문제

В одном очень большом городе устраивают необычные скачки. От обычных скачек они отличаются тем, что проходят не на ипподроме, а на специально заготовленной трассе. Она представляет из себя бесконечную прямую на плоскости.

Трасса очень длинная, поэтому соревнования могут затягиваться не на один день и проходить не только днем, но и ночью. Организаторы глубоко задумались о том, как они будут освещать трассу, ведь освещать бесконечно длинную трассу не так уж и просто. Для этого они закупили $N$ прожекторов, которые будут установлены в некоторых точках города. Известно что прожекторы освещают землю, образуя круги.

Так получилось, что компания, которая устанавливала оборудование, перепутала места установки, поэтому некоторые прожекторы могут вообще не освещать трассу. Теперь соревнование может потерпеть неудачу, организаторы очень обеспокоены тем, что зрители не увидят самые интересные моменты соревнований из-за ошибки мастеров. Помогите организаторам выяснить, какова длина освещенной части трассы.

입력

Первая строка входного файла содержит четыре числа $x\_1,\ y\_1,\ x\_2,\ y\_2$ --- координаты двух точек на прямой. Во второй --- строке число $N$ ( $1 \le N \le 100000$ ) --- количество прожекторов. В каждой их следующих $N$ строк заданы 3 числа $x$ , $y$ и $R$ , координаты и радиус кругов, образованных прожекторами.

Все координаты и радиусы --- целые числа, не превышающие по модулю $10^5$ .

출력

В выходной файл выведите ответ на задачу, с точностью до $10^{-4}$ .

힌트

Этот рисунок соответствует второму примеру. Отмеченная жирной линией часть дороги, является освещенной.

예제2

예제 1
입력
```
0 0 1 1
1
5 5 1
```
예상 출력
```
2.0000
```
예제 2
입력
```
1 1 2 3
3
5 5 5
-5 5 8
-3 -5 3
```
예상 출력
```
18.4460
```