34041번 - 회전체와 쿼리 스페셜 저지

문제

1ドル$번 점부터 $N$번 점까지 반시계 방향으로 번호가 매겨져 있는 점들을 이어 만든 볼록 다각형이 있을 때, 다음 쿼리를 수행하는 프로그램을 작성해 보자.

• $i$ $j$: $i$번 점과 $j$번 점을 잇는 선분으로 볼록 다각형을 분할한다. 분할한 두 다각형에 대해 두 점을 지나는 직선을 기준으로 회전시켜 생긴 회전체를 각각 $A,ドル $B$라고 하자. $A$와 $B$ 중 부피가 작은 회전체의 부피를 출력한다. 만약 두 개의 다각형으로 분할되지 않는다면 0을 출력한다. $(i \ne j)$

입력

첫째 줄에 볼록 다각형의 꼭짓점을 포함하여 변에 위치한 점 $N$개가 주어진다.

둘째 줄부터 $N$개의 줄에 걸쳐 각 점의 좌표 $(x_i, y_i)$를 나타내는 두 정수 $x_i,ドル $y_i$가 공백으로 구분되어 주어진다. $N$개의 점은 반시계 방향으로 주어진다. 연속한 세 점이 일직선 위에 놓일 수도 있음에 유의하라.

$N+2$째 줄에 쿼리의 개수 $Q$가 주어진다.

$N+3$째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다.

출력

각 줄에 쿼리의 답을 한 줄에 하나씩 순서대로 출력한다. 실제 정답과 출력값의 절대오차 또는 상대오차가 10ドル^{-6}$ 이하이면 정답이다.

제한

• 3ドル \leq N \leq 100,000円$
• $-10^6 \leq x_i, y_i \leq 10^6$ $(1 \leq i \leq N)$
• 1ドル \leq Q \leq 100,000円$

힌트

볼록 다각형은 모든 내각이 0ドル$도보다 크고 180ドル$도와 같거나 작은 단순 다각형이다.