수족관 배수

아래 그림 1은 수족관을 정면에서 본 모습입니다. 수족관에는 물이 가득 차 있습니다. 수족관 바닥(수평선분)에 구멍을 하나 뚫으면 그 구멍으로 물이 빠져나갑니다.

그림 1. 수족관과 구멍.

좌표축은 그림처럼 정합니다. $x$축은 왼쪽에서 오른쪽으로 갈수록 커지고, $y$축은 위에서 아래로 갈수록 커집니다. 바닥의 어떤 수평선분에 구멍이 있으면, 그 수평선분의 $y$좌표보다 위쪽(즉 $y$좌표가 그 값 이하)에 있으면서 중력을 따라 그 구멍까지 흘러갈 수 있는 물은 모두 구멍으로 빠져나갑니다. 그래서 그림 1의 수족관은 바닥 구멍을 통해 물이 남김없이 빠집니다.

물의 양은 물이 차지하는 넓이와 같고 단위는 L(리터)입니다. 그림 1의 수족관을 가득 채우면 물의 양은 넓이와 같은 $40$L입니다.

구멍 하나로는 $1$초에 $1$L씩 물이 빠집니다. 따라서 그림 1에서는 $40$초 만에 물이 모두 빠집니다.

그림 2처럼 바닥이 더 복잡할 수도 있습니다.

수족관 바닥은 수평선분과 수직선분이 번갈아 이어지는 형태입니다. 또한 그림 2처럼 수족관을 바로 위에서 수직으로 내려다보면 바닥의 모든 수평선분이 빠짐없이 보입니다.

구멍은 하나 이상 있으며, 항상 수평선분 위에, 그리고 그 수평선분의 한가운데에만 뚫립니다. 하나의 수평선분에는 구멍이 최대 한 개까지 있을 수 있습니다.

그림 2. 처음 상태. 물의 양은 $26$L, 구멍은 $2$개.

그림 2에는 두 수평선분에 구멍이 하나씩, 모두 $2$개(1번, 2번)가 있습니다. 처음 물의 양은 $26$L입니다. $0$초부터 두 구멍으로 물을 빼기 시작하면 몇 초 뒤에 물이 더는 빠지지 않을까요?

그림 3. 물이 빠지는 도중의 상태.

먼저 1번 구멍이 있는 수평선분보다 위에 있는 물 $16$L가 1번과 2번 구멍으로 동시에 빠집니다. 두 구멍으로 $16$L가 나가므로 $8$초 뒤에는 그림 3의 상태가 됩니다.

그다음에는 $3$L의 물이 2번 구멍으로만 $3$초 동안 빠집니다. 결국 $8 + 3 = 11$초 동안 물이 빠지고 그 뒤로는 더 빠지지 않습니다. $11$초 뒤 남은 물은 $7$L이며 최종 상태는 그림 4와 같습니다.

그림 4. 최종 상태.

물이 가득 찬 수족관 바닥의 모양과 구멍이 있는 수평선분들이 주어질 때, 물이 다 빠지는 데 걸리는 시간(초)과 남은 물의 양을 구하는 프로그램을 작성하세요.

첫째 줄에 수족관 경계를 이루는 꼭짓점의 개수 $N$ ($4 \le N \le 300{,}000$)이 주어집니다. $N$은 짝수입니다. 경계는 항상 꼭짓점 $(0, 0)$에서 시작해 꼭짓점 $(A, 0)$에서 끝납니다. 즉 시작 꼭짓점과 마지막 꼭짓점의 $y$좌표는 모두 $0$입니다. 모든 좌표는 $0$ 이상 $500{,}000$ 이하의 정수입니다.

경계의 변은 꼭짓점 $(0, 0)$에서 수직선분으로 시작해, 수평선분과 수직선분이 번갈아 나오다가 수직선분으로 끝납니다. 따라서 수직선분이 수평선분보다 항상 하나 더 많습니다.

둘째 줄부터 $N$개의 줄에 걸쳐, 경계 꼭짓점 $N$개의 $x$좌표와 $y$좌표가 공백으로 구분되어 한 줄에 하나씩, 첫 꼭짓점 $(0, 0)$부터 시계 반대 방향 순서로 주어집니다.

그다음 줄에는 구멍의 개수 $K$ ($1 \le K \le N/2$)가 주어집니다. 이어지는 $K$개의 줄에는 각 구멍이 있는 수평선분의 두 끝 꼭짓점 좌표가 a b c b 형식으로 주어집니다. 이는 구멍이 꼭짓점 $(a, b)$와 $(c, b)$를 잇는 수평선분 위에 있다는 뜻이며 항상 $a < c$입니다.

두 줄을 출력합니다. 첫째 줄에는 구멍으로 물이 다 빠지는 데 걸리는 시간(초)을 소수점 셋째 자리에서 반올림하여 둘째 자리까지 출력합니다. 둘째 줄에는 남은 물의 양을 $0$ 이상의 정수로 출력합니다.

중간 계산값이 $32$비트 정수 범위를 넘을 수 있으므로 필요하면 $64$비트 정수를 사용하세요. 실수 계산에는 double형을 권장합니다.