수족관 2 Batch Compilation commands

아래 그림 1은 수족관을 앞에서 본 모양이다. 이 수족관에는 물이 가득 차 있다. 만약 수족관 밑바닥(수평선분)에 구멍을 하나 뚫으면, 구멍을 통해 수족관 안의 물이 빠지게 된다.

그림 1에서 보는 것처럼, $X$-축은 왼쪽에서 오른쪽으로 증가하고, $Y$-축은 위쪽에서 아래쪽으로 증가한다. 바닥을 나타내는 수평선분에 구멍이 있다면, 그 수평선분의 $y$-좌표와 같거나 작은 위치에 있으면서, 중력에 따라 구멍으로 흘러 들어갈 수 있는 위치에 있는 물은 모두 그 구멍을 통해 외부로 배출된다. 따라서 그림 1의 수족관의 물은 바닥의 구멍을 통해 남김없이 모두 빠진다.

수족관에 담긴 물의 양은 물이 차지하는 면적과 일치하는 양이다. 물의 양의 단위는 L(리터)이다. 따라서 그림 1에서 수족관에 물을 가득 채우면 물의 양은 물이 차지하는 면적과 동일한 40L이다.

하나의 구멍을 통해 1초당 1L의 물이 빠져나간다고 하자. 그러면, 그림 1의 경우에는 40초만에 물이 모두 빠진다.

그림 2처럼 수족관의 바닥이 복잡할 수도 있다.

수족관 바닥은 수평선분과 수직선분이 번갈아 나타나는 형태이다. 또한 아래 그림 2처럼 수족관 위에서 수직방향으로 수족관 바닥을 보았을 때, 수족관의 바닥이 모두 보이는 (즉, 모든 수평선분이 보이는) 형태이다.

수족관에는 하나 이상의 구멍이 존재하는데, 구멍은 수평선분에만 존재하며, 수평선분의 한 가운데에만 위치한다. 그리고 하나의 수평선분에는 최대 하나의 구멍만 존재할 수 있다.

그림 2에는 2개의 수평선분에 총 2개의 구멍(1번 구멍과 2번 구멍)이 뚫려 있다. 처음 물의 양은 26L이다. 2개의 구멍을 통해, 0초부터 물을 빼기 시작하면 몇 초 후부터 더 이상 물이 빠지지 않게 될까?

우선, 1번 구멍이 놓인 수평선분의 위쪽 부분에 있는 물 16L가 1번 구멍과 2번 구멍을 통해 동시에 빠져 나가게 된다. 16L가 두 개의 구멍을 통해 배출되므로, 8초 후에는 그림 3과 같은 상태가 된다.

이후에는 3L의 물이 2번 구멍을 통해 3초 동안 배출된다. 결국, 8초+3초 = 11초 동안 물이 배출되고, 그 이후에는 더 이상 배출되지 않는다. 11초 후에 남은 물의 양은 7L이며, 최종 상태는 그림 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$개의 줄에는 각 구멍이 존재하는 수평선분의 양 끝 꼭짓점의 $x$-좌표와 $y$-좌표 값이 빈 칸을 사이에 두고 차례로 주어진다. 즉, 어떤 구멍이 위치한 수평선분의 정보가 $a$ $b$ $c$ $b$로 주어졌다면, 구멍이 위치한 수평선분은 꼭짓점 $(a, b)$와 꼭짓점 $(c, b)$를 연결한 선분이라는 의미이다. 항상 $a < c$이다.

출력 형식

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

유의 사항

중간 계산 결과 값이 32비트 정수형 범위를 벗어날 수 있으니 필요하면 64비트 정수형을 이용할 것을 권장한다. 실수형은 double형을 사용할 것을 권장한다.

부분문제의 제약 조건

• 부분문제 1: 전체 점수 100점 중 13점에 해당하는 데이터에 대해, $N \le 10, K \le 1,$ 좌표값 $\le 100$이다.
• 부분문제 2: 전체 점수 100점 중 21점에 해당하는 데이터에 대해, $K \le 100, $ 좌표값 $\le 500$이다.
• 부분문제 3: 전체 점수 100점 중 35점에 해당하는 데이터에 대해, $N \le 5,000$이다.
• 부분문제 4: 전체 점수 100점 중 31점에 해당하는 데이터에 대해, 추가 제약 조건은 없다.

입력과 출력의 예

예제 1

입력

4
0 0
0 5
8 5
8 0
1

출력

40

예제 2

입력

14
0 0
0 5
1 5
1 3
2 3
2 4
3 4
3 2
5 2
5 4
6 4
6 3
8 3
8 0
2

출력

25