eolymp
bolt
Try our new interface for solving problems
Problems

Shelter

Shelter

Taro lives in a town with \textbf{N} shelters. The shape of the town is a convex polygon. He’ll escape to the nearest shelter in case of emergency. Given the current location, the cost of escape is defined as the square of the distance to the nearest shelter. Because emergency occurs unpredictably, Taro can be at any point inside the town with the same probability. Calculate the expected cost of his escape. \InputFile The first line contains two integers \textbf{M} and \textbf{N} (\textbf{3} ≤ \textbf{M} ≤ \textbf{100}, \textbf{1} ≤ \textbf{N} ≤ \textbf{100}), which denote the number of vertices of the town and the number of shelters respectively. The following \textbf{M} lines describe the coordinates of the vertices of the town in the conunter-clockwise order. The \textbf{i}^th line contains two integers \textbf{x_i} and \textbf{y_i} (\textbf{1000} ≤ \textbf{x_i}, \textbf{y_i} ≤ \textbf{1000}), which indicate the coordinates of the \textbf{i}^th vertex. You may assume the polygon is always simple, that is, the edges do not touch or cross each other except for the end points. Then the following \textbf{N} lines describe the coordinates of the shelters. The \textbf{i}^th line contains two integers \textbf{x_i} and \textbf{y_i}, which indicate the coordinates of the \textbf{i}^th shelter. You may assume that every shelter is strictly inside the town and any two shelters do not have same coordinates. \OutputFile Output the expected cost in a line. The answer with an absolute error of less than or equal to \textbf{10^\{-4\}} is considered to be correct.
Time limit 1 second
Memory limit 64 MiB
Input example #1
4 1
0 0
3 0
3 3
0 3
1 1
Output example #1
2.0000000000
Source The 2011 35th Annual ACM Programming Contest Winter Camp