eolymp
bolt
Try our new interface for solving problems

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.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
4 1
0 0
3 0
3 3
0 3
1 1
Çıxış verilənləri #1
2.0000000000
Mənbə The 2011 35th Annual ACM Programming Contest Winter Camp