9047: Typhoon
内存限制：128 MB
时间限制：3 S
题面：传统
评测方式：文本比较
上传者：
提交：3
通过：2
题目描述
A terrible typhoon is about to make landfall, and you decide to leave your home and seek refuge.
We can regard the problem as occurring on a two-dimensional plane. You have n alternative shelters, and
you need to choose one to go to. Specifically, the i-th shelter is located at point (Xi
, Yi) .
Now the meteorological station gives the predicted typhoon track, which consists of m forecast points
(x1, y1),(x2, y2), . . . ,(xm, ym) , where (x1, y1) is the starting point and (xm, ym) is the ending point.
According to the forecast, the center of the typhoon will moves along the segments between two adjacent
points in turn.
In order to simplify the model, it is assumed that the influence range of typhoon is a circle with radius
r and the radius will never change during the move. If a point will be within or just on the boundary of
the typhoon’s influence range at a certain time, then we consider this point to be unsafe.
The radius of a typhoon is unpredictable. So you want to know, for each shelter, what is the minimum
typhoon radius that still makes it unsafe.
输入格式
Please note that unlike other problems, there is only one test case input for this problem.
The first line contains two integers m, n (2 ≤ m, n ≤ 104
), indicating the number of forecast points of the
typhoon track and the number of shelters.
Then the following m lines, each line contains two integers xi
, yi (|xi
|, |yi
| ≤ 109
), indicating the coordinates
of the i-th forecast points of the typhoon track.
Then the following n lines, each line contains two integers Xi
, Yi (|Xi
|, |Yi
| ≤ 109
), indicating the
coordinates of the i-th shelter.
输出格式
Output n lines, the i-th line contains a single real number ri
, represents the answer for the i-th shelter.
All the real number you output should be rounded into 4 decimals.
输入样例 复制
7 3
10 0
6 1
4 1
4 2
3 2
3 3
0 8
2 3
5 3
6 0输出样例 复制
0.8575
1.4142
0.9701
数据范围与提示
The result of the sample is shown as the following image:
