题目描述
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 $(X_i, Y_i)$ .
Now the meteorological station gives the predicted typhoon track, which consists of $m$ forecast points $(x_1,y_1),(x_2,y_2),\dots,(x_m,y_m)$ , where $(x_1,y_1)$ is the starting point and $(x_m,y_m)$ 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
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 $(X_i, Y_i)$ .
Now the meteorological station gives the predicted typhoon track, which consists of $m$ forecast points $(x_1,y_1),(x_2,y_2),\dots,(x_m,y_m)$ , where $(x_1,y_1)$ is the starting point and $(x_m,y_m)$ 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\le m,n\le 10^4)$, 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 $x_i,y_i\ (|x_i|,|y_i|\le 10^9)$, indicating the coordinates of the $i$-th forecast points of the typhoon track.
Then the following $n$ lines, each line contains two integers $X_i,Y_i\ (|X_i|,|Y_i|\le 10^9)$, indicating the coordinates of the $i$-th shelter.
The first line contains two integers $m,n\ (2\le m,n\le 10^4)$, 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 $x_i,y_i\ (|x_i|,|y_i|\le 10^9)$, indicating the coordinates of the $i$-th forecast points of the typhoon track.
Then the following $n$ lines, each line contains two integers $X_i,Y_i\ (|X_i|,|Y_i|\le 10^9)$, indicating the coordinates of the $i$-th shelter.
输出
Output $n$ lines, the $i$-th line contains a single real number $r_i$ , represents the answer for the $i$-th shelter.
All the real number you output should be rounded into 4 decimals.
All the real number you output should be rounded into 4 decimals.
样例输入 Copy
7 3
10 0
6 1
4 1
4 2
3 2
3 3
0 8
2 3
5 3
6 0
样例输出 Copy
0.8575
1.4142
0.9701
提示
The result of the sample is shown as the following image:
