ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Junior Contest October'2002

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Exactness of Projectile Hit

Time limit: 1.0 second
Memory limit: 64 MB
Inexactness of projectile hit may be compensated
by increasing of the projectile diameter.
Sergey Sizy
Problem illustration
In the problem you are to determine the minimal diameter that may compensate inexactness of projectile hit in each concrete case. Assume that all the targets are convex polygons. A hit is the situation when the circle crater that the projectile leaves (the crater diameter equals to the one of the projectile) covers at least one point of the target.


The first line contains three numbers — coordinates of the hit point of the projectile center and the number of polygon sides N (3 ≤ N ≤ 100). The next N lines contain the vertices coordinates in counter-clockwise order. All the coordinates are integers from [−2000,2000].


You are to output the only number which is the minimal diameter of a projectile that will cover the target rounded with three digits after the decimal point.


2 -1 8
0 1
1 0
2 0
3 1
3 2
2 3
1 3
0 2
Problem Author: Anton Botov and Anatoly Uglov
Problem Source: USU Open Collegiate Programming Contest October'2002 Junior Session
To submit the solution for this problem go to the Problem set: 1215. Exactness of Projectile Hit