N-Queen (넓이)

시간 제한1초메모리 제한1024 MB

요약

볼록 사각형 안에 놓인 N×N 격자에서 서로 공격하지 않도록 퀸 N개를 배치할 때, 퀸이 차지하는 칸 넓이의 합이 최대가 되는 값을 구합니다.

문제

N-Queen 문제는 크기가 $N \times N$ 인 체스판 위에 퀸 $N$ 개를 서로 공격하지 못하도록 놓는 문제이다. 퀸은 같은 행, 같은 열, 또는 같은 대각선 위에 있는 다른 기물을 공격할 수 있다.

이 문제에서는 체스판이 찌그러져 있다. 체스판은 그림과 같은 볼록사각형 ABCD이다. 사각형의 네 변을 각각 $N$ 등분하고, 선분 AB와 CD, 선분 AD와 BC에 있는 등분점 중 마주 보는 점끼리 이어서 $N^2$ 개의 사각형 칸을 만든다.

퀸 $N$ 개를 서로 공격하지 못하도록 놓는 방법 가운데, 퀸이 위치한 칸의 넓이의 합이 최대가 되는 경우를 구하자.

첫째 줄에 $N$ 이 주어진다.

둘째 줄에 네 꼭짓점 A, B, C, D의 좌표 $x_A, y_A, x_B, y_B, x_C, y_C, x_D, y_D$ 가 공백으로 구분되어 주어진다. 점의 순서는 시계방향 또는 반시계방향이다.

퀸이 위치한 칸의 넓이의 합이 가장 클 때의 값을 출력한다. 절대오차 또는 상대오차는 $10^{-9}$ 까지 허용한다.