30921번 - 🧩 N-Queen (Area) 스페셜 저지

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓는 문제이다. 퀸은 같은 행, 열, 또는 대각선 위에 있는 다른 기물을 공격할 수 있다.

이 문제에서는 체스판이 찌그러져 있다. 즉 체스판은 그림과 같은 볼록사각형 ABCD로, 사각형의 네 변을 N등분하고, 네 선분 AB와 CD, AD와 BC에 있는 N − 1개의 등분점들을 마주 보는 것끼리 이어서 만들어진 N²개의 사각형 칸으로 구성된다.

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

입력

첫째 줄에 N이 주어진다.

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

출력

첫째 줄에 퀸이 위치한 칸의 넓이의 합이 가장 클 때의 값을 출력한다. 절대/상대오차는 10⁻⁹까지 허용한다.

제한

• 4 ≤ N ≤ 100. 이 범위에서 항상 퀸 N개를 놓을 수 있는 방법이 있음이 보장된다.
• −1000 ≤ x_A, y_A, x_B, y_B, x_C, y_C, x_D, y_D ≤ 1000
• 모든 입력은 정수이다.

힌트