#GYM104639K. Minimum Euclidean Distance
Minimum Euclidean Distance
Description
One day you are surviving in the wild. After a period of exploration, you determine a safe area, which is a convex hull with $n$ vertices $P_1,P_2,\dots,P_n$ in counter-clockwise order and any three of them are not collinear.
Now you are notified that there will be $q$ airdrop supplies, and for the $i$-th supply, its delivery range is described by a circle $C_i$ , which means the supply will landed with uniformly probability among all the points with a real number coordinate inside $C_i$.
You need supplies so much that you decide to predetermine a starting point for each supply, and the starting point of two different supplies can be different. Every starting point should be inside the safe area and have the smallest expected value of the square of the Euclidean distance to the corresponding supply landing point.
Recall that On a two-dimensional plane, the Euclidean distance between two points $(x_1,y_1)$ and $(x_2,y_2)$ is $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$. If both coordinates of a point are all integers, then we call this point an integer point.
The first line contains two integers $n, q\ (3\le n,q\le 5000)$ , representing the number of vertices of the safe area and the number of airdrop supplies.
The following $n$ lines, each line contains two integers $x_i,y_i$ , representing the coordinates of the $i$-th vertex of the safe area.
It's garanteed that the vertices are given in counter-clockwise order and any three of them are not collinear.
Then the following $q$ lines, each line contains $4$ integers $x_{i,1},y_{i,1},x_{i,2},y_{i,2}$, representing the segment connecting $(x_{i,1},y_{i,1})$ and $(x_{i,2},y_{i,2})$ is a diameter of the circle $C_i$.
All the coordinates input are integers in the range $[-10^9, 10^9]$ .
For each airdrop supply, output a single line with a real number - the minimum expected value of the square of the Euclidean distance. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-4}$. That is, if your answer is $a$, and the jury's answer is $b$, then the solution will be accepted if $\frac{|a-b|}{\max (1,|b|)} \leq 10^{-4}$ .
Input
The first line contains two integers $n, q\ (3\le n,q\le 5000)$ , representing the number of vertices of the safe area and the number of airdrop supplies.
The following $n$ lines, each line contains two integers $x_i,y_i$ , representing the coordinates of the $i$-th vertex of the safe area.
It's garanteed that the vertices are given in counter-clockwise order and any three of them are not collinear.
Then the following $q$ lines, each line contains $4$ integers $x_{i,1},y_{i,1},x_{i,2},y_{i,2}$, representing the segment connecting $(x_{i,1},y_{i,1})$ and $(x_{i,2},y_{i,2})$ is a diameter of the circle $C_i$.
All the coordinates input are integers in the range $[-10^9, 10^9]$ .
Output
For each airdrop supply, output a single line with a real number - the minimum expected value of the square of the Euclidean distance. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-4}$. That is, if your answer is $a$, and the jury's answer is $b$, then the solution will be accepted if $\frac{|a-b|}{\max (1,|b|)} \leq 10^{-4}$ .
4 3
0 0
1 0
1 1
0 1
0 0 1 1
1 1 2 2
1 1 2 3
0.2500000000
0.7500000000
1.8750000000