<PREV Problem:
NEXT>
Solved by 58 users: ...
UserDateAttemptTimeCMSC
DAV08 oct 2010C++1300.01569 
DAV06 oct 2010C++1200.01598 
mukel30 aug 2011C++300.01635 
fetetriste20 dec 2009C++500.02656 
Dmitry_Gozman24 nov 2005Kylix400.01657 
fetetriste20 dec 2009C++400.01662 
Artur07 nov 2006Kylix300.02716 
Evgeny10 jun 2004C++3?.??731 
dragonghy03 apr 2007FPC100.07745 
zmy24 dec 2007C++100.01760 
shangjingbo17 oct 2008C++100.01760 
abortmozga.ru09 oct 2010C++1200.02810 
Languages
C++
36
Kylix
10
FPC
9
C
2
Java
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Mine field

Time limit = 5 seconds

Petya have found himself standing in a minefield in a point A. He needs to go to a point B.

He knows all mines positions but he would like his way (smooth curve) lies as far from mines as possible.

Please, help him. Write a program that finds maximal R for witch the following condition is satisfied: there is smooth curve from A to B witch stay away from all mines more (or equal to) than distance R.

Input Line 1: Coordinates of the point A.
Line 2: Coordinates of the point B.
Line 3: M — number of mines. 1 ≤ M ≤ 30.
Lines 4, ...,M+3 : Coordinates of mines.
All coordinates are real numbers less than 100000 and greater than -100000

Output Line 1: R. Two or more digits after point.

Input#1
0 0
3 3
2
1 1
2 2
Output#1
1.41

Input#2
-10 0
0 0
4
1 1
1 -1
-1 1
-1 -1
Output#2
1.00

Author:
Voroztsov Artem
4 October 2003

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 3.233.215.196