다각형 축소 키트

다각형 축소 키트는 엔로고니아의 기하 마법 수업에서 자주 쓰는 도구다. 키트는 좌표평면 위의 두 점 $A$, $B$로 이루어져 있다.

꼭짓점이 순서대로 $1, 2, \ldots, N$인 볼록다각형이 있다. 키트로 이 다각형을 축소하려면 규칙을 지켜야 한다. 각 꼭짓점 $x$는 정확히 한 번 옮기며, 선분 $Ax$의 중점이나 선분 $Bx$의 중점 중 하나로 옮긴다. 옮긴 결과는 원래 꼭짓점의 상대적인 순서를 유지하는 볼록다각형이어야 한다. 즉 키트를 적용하는 모든 방법 가운데 옮긴 꼭짓점 $1, 2, \ldots, N$을 이 순서대로 이었을 때 볼록다각형이 되는 방법만 올바르다. 원래 다각형이 시계 방향이고 올바른 축소 결과가 같은 꼭짓점 순서로 반시계 방향이어도 된다. 방향은 상관없고 점의 상대적인 순서만 중요하다.

이 문제에서 옮긴 점 $Q_1, Q_2, \ldots, Q_N$이 이 순서대로 볼록다각형을 이룬다는 것은 다음 조건을 모두 만족한다는 뜻이다. ($Q_{N+1} = Q_1$, $Q_0 = Q_N$으로 본다.)

1. 모든 $i$에 대해 이웃한 두 점 $Q_i$와 $Q_{i+1}$은 서로 다르다.
2. 모든 꼭짓점 $Q_i$에서 경계는 같은 방향(모두 왼쪽 또는 모두 오른쪽)으로 꺾이거나 똑바로 나아간다. 똑바로 나아간다는 것은 $Q_{i-1}$, $Q_i$, $Q_{i+1}$이 한 직선 위에 있고 $Q_i$가 나머지 두 점 사이에 있다는 뜻이다. 한 직선 위에서 되돌아가는 경우는 허용하지 않는다.
3. 경계는 정확히 한 바퀴 돈다. 즉 결과는 스스로 교차하지 않는 단순다각형이다.

점 하나나 직선은 다각형으로 보지 않는다. 따라서 키트를 쓴 결과가 볼록다각형이 아니면 그 사용법은 올바르지 않다.

기하 마법은 대부분의 학생에게 어려운 과목이다. 선생님은 학생들에게 볼록다각형 하나를 주고 키트로 축소해서 넓이를 최대한 작게 만들라고 했고, 친구가 이 문제를 대신 풀어 달라고 부탁했다. 올바른 사용법으로 얻을 수 있는 다각형의 최소 넓이를 구하라.

위 그림은 키트를 올바르게 사용한 예다. 색칠된 다각형은 꼭짓점 순서를 유지하는 다각형 가운데 넓이가 가장 작은 것이고, 점 $A$와 $B$는 키트의 두 점이다. 이름은 축소 키트지만 키트를 써서 다각형의 넓이가 커지는 경우도 있다. 기하는 어렵다!

첫째 줄에 다각형의 꼭짓점 개수 $N$이 주어진다. 다음 $N$개의 줄에는 꼭짓점의 좌표를 나타내는 두 정수 $x$, $y$가 한 줄에 하나씩 주어진다. 마지막 줄에는 네 정수 $A_x$, $A_y$, $B_x$, $B_y$가 주어진다. 차례대로 점 $A$의 $x$좌표와 $y$좌표, 점 $B$의 $x$좌표와 $y$좌표다.

꼭짓점은 다각형 위에 나타나는 순서대로 시계 방향이나 반시계 방향으로 주어진다. 같은 점이 두 번 주어지지 않으며, 주어진 다각형은 위에서 정의한 볼록다각형이다. 연속한 세 꼭짓점이 한 직선 위에 있을 수도 있다.

제한

• $3 \le N \le 10^5$
• $-10^6 \le x, y \le 10^6$
• $-10^6 \le A_x, A_y, B_x, B_y \le 10^6$

올바른 사용법으로 얻을 수 있는 다각형의 최소 넓이를 소수점 아래 셋째 자리까지 한 줄에 출력한다.

모든 꼭짓점을 선분 $Ax$의 중점으로 옮기면 원래 다각형을 평행이동하고 절반으로 줄인 다각형이 되므로 올바른 사용법은 항상 있다. 옮긴 점의 좌표는 모두 정수의 절반이어서 넓이는 항상 $\frac{1}{8}$의 배수다. 따라서 답은 소수점 아래 셋째 자리까지 정확하게 나타낼 수 있고 반올림은 필요 없다.