ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2013

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Location Generator

Time limit: 1.0 second
Memory limit: 64 MB
‘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 (−106xi, 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.


0 0
1 0
1 1
0 1
Problem Author: Denis Dublennykh
Problem Source: Ural Sport Programming Championship 2013
To submit the solution for this problem go to the Problem set: 1973. Location Generator