|Online Judge||Problem Set||Authors||Online Contests||User|
Mr. X wants to travel from a point A(Xa, Ya) to a point B(Xb, Yb), A ≠ B. 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.
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.
The output has to contain a single floating point number.
0 0 8 0 2 0 4 5 8 4 5
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