333. Random Shooting
Time limit per test: 0.25
Memory limit: 65536
You're playing a new game at the shooting range. First, a target is placed on a square board. The target itself is a convex polygon strictly inside the board.
Then, you're allowed to shoot twice. In case at least one of your shots gets inside the target, you win. Moreover, if the segment connecting the points of your shots intersects the target, you still win. If none of the above holds, you lose.
Assuming your aiming is very bad (i.e., the points of your shots are independently uniformly distributed all over the board), compute the probability of you winning.
The first line of input contains an integer N
, 3 ≤ N
≤ 8, — the number of vertices of the target. The next N
lines contain two integers each, xi
, 1 ≤ xi
≤ 99, decribing the coordinates of the vertices of the target (a convex polygon) in the counter-clockwise direction. No three vertices of the target lie on the same line. The coordinate system is chosen so that the corners of the board have coordinates (0, 0), (0, 100), (100, 0) and (100, 100).
Output the required probability. Your solution will be accepted if it is within 10-7
of the correct one.