Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
GSM phone
Time Limit: 5000MSMemory Limit: 65536K
Total Submissions: 333Accepted: 49
Case Time Limit: 2000MSSpecial Judge

Description

Mr. X wants to travel from a point A(Xa, Ya) to a point B(Xb, Yb), AB. He has a GSM mobile phone and wants to stay available during whole the trip. A local GSM operator has installed K sets of GSM equipment in points Pi(Xi, Yi),  1 ≤ i ≤ K. Each set of the equipment provides circular zone Zi. Point Pi is the center of the zone Zi and Ri is its radius. Mobile phones can operate inside such a zone and on its border. Zones can intersect, but no zone completely includes another one.

Your task is to find the length of the shortest way from A to B which is completely covered by GSM zones. You may assume that such a way always exists. Precision of calculations has to be 0.00001.

Input

The first line contains four floating point numbers Xa Ya Xb Yb, separated by one or more spaces. The next line contains single integer number K (K ≤ 200). Each of the rest K lines of the file contains three floating point numbers Xi, Yi, Ri separated by one or more spaces. Ri > 0.

Output

The output has to contain a single floating point number.

Sample Input

0 0 8 0
2
0 4 5
8 4 5

Sample Output

8.24621

Source

Northeastern Europe 2003, Western Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator