‘What are you thinking about?’
‘I’m trying to invent a location generator for my level. It’s one of the first levels, so I need something simple.
I’ve got a map in the form of a convex polygon, and I must place on it two players and some obstacles to separate them.
But if there’re too many obstacles, the location will be inconvenient for the game.’
‘Fix some vertex A of your polygon. Then if you choose random points B and C strictly inside the polygon,
you’ll get a triangle ABC (it may be degenerate).
Make this triangle impassable and place the players near point A on different sides of the triangle.’
‘Won’t this impassable zone be too big? The players need enough free space for moving.’
‘It seems that the area of this zone is on average rather small compared the area of the whole map. Let’s estimate it.’
The first line contains the number n (3 ≤ n ≤ 1 000) of the vertices of the polygon.
The i-th of the following n lines contains integers xi and yi (−106 ≤ xi, yi ≤ 106), which are the coordinates of the i-th vertex
in the counterclockwise order. No three vertices of the polygon lie on the same line.
The fixed vertex of the polygon is the one given first in the input.
Output the average area of the impassable zone constructed by the proposed method,
if two triangle vertices are chosen uniformly from the interior of the polygon.
The absolute or relative error of the answer should not exceed 10−6.
Problem Author: Denis Dublennykh
Problem Source: Ural Sport Programming Championship 2013