보물섬

문제 정보

문제

위대한 해적 가이브러시 포피우드가 위대한 보물 투피스를 숨겨뒀다는 보물섬을 오랜 고난을 거쳐 찾아냈습니다. 가이브러시는 이 보물섬 어디엔가 투피스를 묻어뒀다고 알려지고 있는데, 그 위치가 어디인지는 모릅니다. 섬을 다 뒤집어 엎기 직전, 지도에는 여백이 부족해 적지 않았던 보물의 위치가 적힌 쪽지를 발견했습니다. 이 쪽지에는 보물이 묻혀 있는 곳이 적혀 있는데, 설명이 길고 장황한 데다 군데 군데 지워져 정확히 알아보기 쉽지 않았습니다. 쪽지를 열심히 연구한 결과, 보물이 묻혀 있는 곳의 범위를 어느 정도 좁힐 수 있었습니다.

treasure2.png

섬의 지도가 위 그림과 같이 N개의 점을 갖는 다각형으로 주어질 때, 보물이 묻혀 있을 수 있는 곳은 두 점 (x1,y1)과 (x2,y2) 를 서로 대칭인 꼭지점으로 갖고, 네 변이 모두 x축 혹은 y축에 평행한 직사각형 내부입니다. 우리는 이 직사각형 내에 포함된 육지를 전부 조사하고 싶습니다. 우리가 조사해야 할 부분의 넓이를 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 다섯 개의 정수로 직사각형의 꼭지점의 좌표 x1 , y1 , x2 , y2 (0 <= x1 < x2 <= 100,0 <= y1 < y2 <= 100) 그리고 섬의 지도를 나타내는 다각형 꼭지점의 수 N (3 <= N <= 100) 이 주어집니다. 그 후 N 줄에 각 2개의 정수로 각 꼭지점의 좌표 Xi , Yi (0 <= Xi, Yi <= 100) 가 주어집니다. 꼭지점은 시계 반대 방향으로 주어지며, 마지막 점은 첫 번째 점과 연결되어 있습니다.

주어진 섬의 면적이 0이거나, 섬의 경계선이 자기 자신과 교차하거나 겹치는 경우는 없습니다.

출력

각 테스트 케이스마다 한 줄에 조사해야 할 육지의 넓이를 출력합니다. 10-7 이하의 절대/상대 오차를 갖는 답은 정답으로 인정됩니다.

예제 입력

2
26 34 76 72 15
41 52
50 71
42 87
26 84
16 58
33 33
51 23
64 32
73 17
86 14
91 38
92 68
82 79
68 45
61 58
50 20 70 80 4
86 50 
30 10
90 50
30 90

예제 출력

1343.0948739496 
57.1428571429

노트

3개의 댓글이 있습니다.