정사영으로 가능한 최대 부피
시간 제한2초메모리 제한128 MB
3차원 입체를 xz평면과 yz평면에 투영한 두 개의 convex 다각형이 주어질 때, 이 투영들과 일치하는 convex 입체의 최대 부피를 구합니다.
문제
3차원 공간에 볼록한 입체도형이 있다. 이 도형을 xz평면과 yz평면에 수직으로 비추면 각각 볼록다각형이 된다.
두 정사영의 모양이 주어질 때, 이 조건을 만족하는 원본 볼록 입체도형의 가능한 최대 부피를 구하라. 두 정사영만으로 원본은 하나로 정해지지 않으므로, 가능한 모든 볼록 입체도형 중 부피가 가장 큰 경우의 값을 출력해야 한다.
입력
첫째 줄에 xz평면에 비친 정사영의 꼭짓점 수 Nxz가 주어진다. (3 <= Nxz <= 1,000)
다음 Nxz개의 줄에는 Pxz의 꼭짓점 좌표 x, z가 시계방향 순서로 공백으로 구분되어 주어진다.
그 다음 줄에 yz평면에 비친 정사영의 꼭짓점 수 Nyz가 주어진다. (3 <= Nyz <= 1,000)
다음 Nyz개의 줄에는 Pyz의 꼭짓점 좌표 y, z가 시계방향 순서로 공백으로 구분되어 주어진다.
모든 좌표의 절댓값은 500 이하이다. 입력으로 주어지는 두 다각형은 모두 볼록다각형이다. 두 다각형의 최소 z좌표와 최대 z좌표는 각각 서로 같다. 각 다각형에서 인접한 두 점은 항상 다르지만, 한 변 위에 있는 세 개 이상의 점이 입력될 수 있다.
출력
첫째 줄에 원본 입체도형의 부피로 가능한 최댓값을 출력한다.
절대 오차 또는 상대 오차가 10^-2 이하이면 정답으로 인정된다.