[2019 SCPC 2차 예선]

드론 탐험

드론으로 동굴을 탐험하려고 한다.

동굴은 2차원 평면의 영역으로 생각하자.



아래 그림과 같이 동굴의 천장과 바닥은 수직인 선분과 수평인 선분들로만 이루어진다고 한다.

어떤 \(x\) 좌표에서도 그 \(x\) 좌표에는 천정(바닥)의 한 점 혹은 한 수직변만 존재한다.

드론은 동굴의 왼쪽 끝의 정해진 높이(그림에서 왼쪽 별표)에서 시작해서 오른쪽 끝의 정해진 높이(그림에서 오른쪽 별표)로 가야 한다. 드론이 움직이는 방법은 아래와 같다.



1.    드론은 수평으로 오른쪽으로 움직일 수 있다. 

2.    드론은 수직으로 아래나 위로 움직일 수 있다.

3.    드론은 위 조건 하에서 가능한 최단 경로로 움직여야 한다.

 



드론이 움직일 수 있는 경로는 아마도 여러가지가 있을 것이다.

드론이 동굴을 탐험하는 것을 무한히 반복해서 모든 가능한 방법으로 움직인 궤적을 다 그리면 어떤 영역이 나올 것이다.

위에서 빗금친 영역이 그러한 영역이 될 것이다.

이 영역의 면적을 계산하는 프로그램을 작성하라.

(드론은 천정이나 바닥에 무한히 가까이 날 수 있으므로 면적을 계산하는 목적으로는 천정이나 바닥에 붙어서 날수 있는 것으로 생각해도 동일하다.)




입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.

파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 \(T\) 가 주어지고,

이후 차례로 \(T\) 개의 테스트 케이스가 주어진다. \((1\le T \le 30)\)

각 테스트 케이스의 첫 줄에는 동굴의 가로 길이 \(L\), 시작 높이 \(S\), 끝 높이 \(E\)가 주어진다.



다음 줄에 천정을 이루는 가로변들의 개수 \(A\)가 주어진다. 다음 \(A\)개의 줄들에, 왼쪽부터 순서대로, 각 가로변의 가로 길이와 높이가 주어진다.

다음 줄에 바닥을 이루는 가로변들의 개수 \(B\)가 주어진다.

다음 B개의 줄들에, 왼쪽부터 순서대로, 각 가로변의 가로 길이와 높이가 주어진다.



드론의 시작 위치는 동굴의 왼쪽 끝이고, 최종 위치는 동굴의 오른쪽 끝이다.

드론의 시작 높이와 끝 높이는 동굴의 천정과 바닥 사이이다. 동굴 전체의 길이 \(L\)을 포함한 모든 가로 길이는 최대 \(10^9\)인 자연수이다.

모든 높이는 절대값이 최대 \(10^9\)인 정수이다. 동굴의 천정은 동굴의 바닥과 단 한 점에서도 만나지 않는다. \(1 \le A, B \le 100,000\)이다.


출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,

각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다.

다음 줄에 계산된 면적을 정수로 출력한다.

입출력예

입력
1
13 6 7
5
3 7
1 1
4 6
4 7
1 8
7
2 2
3 0
1 1
1 2
1 3
1 0
4 3
출력
Case #1
50

돌아가기

댓글