Making a Flyswatter
Time limit1sMemory limit1024 MB
Given a simple polygon, find the expected squared distance between two points chosen independently and uniformly inside it.
- Level
Hard8 of 10
- Topics
- Geometry, Math, Prefix sum, Combinatorics
- Solved
- No attempts yet
Problem
Silver was writing a problem for SNUPC in a polygonal room. Unable to come up with an idea, he happened to look up, and at that moment he found two mosquitoes stuck to the ceiling! Silver, who had suffered a lot from mosquitoes, fought a fierce battle with them but could not catch them in the end. Yet the next day, and the day after that, the same two mosquitoes were stuck to the ceiling. To catch these two mosquitoes, Silver decided to make a custom DIY flyswatter.
The flyswatter is circular and made of a special material perfect for catching mosquitoes: even a light touch kills a mosquito instantly. This material also folds well, so a mosquito can be caught without trouble even when it sits on an edge or a vertex. However, once the flyswatter is swung at the ceiling, any mosquito it does not hit runs away. Therefore, to kill both mosquitoes in one swing, the diameter of the flyswatter must be at least the distance between the two mosquitoes. The unit price of the special material is 4/π per unit area. That is, for a distance d between the two mosquitoes, the cost of making the flyswatter is d2.
Happy at the thought of making the flyswatter and catching the mosquitoes, Silver wrote this problem! When two mosquitoes are at arbitrary positions on the ceiling, what is the expected cost of making the flyswatter? Each mosquito is at an arbitrary point inside the polygon (the ceiling) with uniform probability. In other words, for any "region with area" S inside the polygon D, the probability that a mosquito lies in S is |S|/|D|, where |A| is the area of figure A. The positions of the two mosquitoes are chosen independently.
Input
The first line gives the number of vertices N of the polygon. (3 ≤ N ≤ 100,000)
The following N lines each give the x- and y-coordinates of a vertex of the polygon, separated by a space. (-10,000 ≤ x, y ≤ 10,000)
The vertices of the polygon are given in counterclockwise order, and the polygon is guaranteed to be simple. That is, no two segments of the polygon intersect except at the shared endpoint of two consecutive segments.
Output
On the first line, print the expected cost of making the flyswatter. An answer with an absolute or relative error of at most 10-6 is accepted.