N-Queen (Area)

The N-Queen problem asks you to place $N$ queens on an $N \times N$ chess board so that no two queens attack each other. A queen can attack other pieces on the same row, column, or diagonal.

In this problem, the chess board is distorted. The board is a convex quadrilateral ABCD, as shown in the figure. Each of the four sides is divided into $N$ equal parts. Division points on segments AB and CD, and on AD and BC, are connected to the points that face them. This forms $N^2$ square cells.

Among all placements of $N$ queens where no two queens attack each other, find the placement that maximizes the total area of the cells occupied by queens. Output that maximum total area.

The first line contains $N$.

The second line contains the coordinates of the four vertices $x_A, y_A, x_B, y_B, x_C, y_C, x_D, y_D$, separated by spaces. The vertices are given in clockwise or counterclockwise order.

Print the maximum total area of the cells occupied by queens. Answers with an absolute or relative error of up to $10^{-9}$ are accepted.

• $4 \le N \le 100$. It is guaranteed that a placement of $N$ queens exists in this range.
• $-1000 \le x_A, y_A, x_B, y_B, x_C, y_C, x_D, y_D \le 1000$
• All input values are integers.