Hide

Problem J
Surveillance

You would like to install a single camera somewhere in the interior of a room. The room is described as a polygon with axis-aligned sides. You would like to ensure that the entire area of the room is visible from the camera, modeled as a point that can see in all directions. The complication is that the walls of the room are actually low-quality flat mirrors, such that any part of the room from which light can reach the camera via at most one reflection is visible from the camera (but not two or more reflections). The corners of the room are not reflective.

Given a description of the room, determine the square footage of the area in which the camera may be placed satisfying this condition.

Input

The first line of input contains a single integer $n$ ($4 \le n \le 6$), which is the number of corners in the room.

Each of the next $n$ lines contains two integers $x$ and $y$ ($|x|,|y| \le 1000$). These are the room’s corners, in counter-clockwise order.

It is guaranteed that the room’s walls and corners do not intersect each other, and that all of the walls are axis-aligned. All measurements are in feet.

Output

Output a single floating point number, which is the square footage of the area in which the camera can be placed such that the camera can see the entire area of the room with at most one reflection from the mirrored walls. This value must be accurate to an absolute or relative error of $10^{-6}$.

Sample Input 1 Sample Output 1
6
0 0
10 0
10 6
4 6
4 10
0 10
58.666666666666664

Please log in to submit a solution to this problem

Log in