강의실 스크린

많은 강의실은 같은 화면을 여러 대의 디스플레이에 동시에 띄웁니다. 기둥이나 앞사람의 머리가 한 화면을 완전히 가리더라도 다른 화면으로 내용을 볼 수 있게 하기 위해서입니다. 그렇다면 앉은 자리에 따라 발표 내용을 실제로 얼마나 볼 수 있을까요?

다음과 같이 모형화합니다. 사람의 머리는 무시하고 건물 구조에 의한 가림만 고려합니다. 강의실은 닫힌 단순 다각형으로 주어지며(벽은 서로 교차하지 않습니다), 평면 위의 여러 스크린이 선분으로, 그리고 다각형 내부의 내 위치가 함께 주어집니다.

모든 스크린은 같은 내용을 보여 주며, 그 내용은 스크린의 왼쪽 끝(내용의 0%)에서 오른쪽 끝(100%)까지 걸쳐 있습니다. 내 위치에서는 어떤 스크린을 전부, 일부만, 또는 전혀 보지 못할 수 있습니다. 볼 수 있는 부분을 모두 합쳤을 때(합집합) 얻는 내용의 총 비율을 구합니다. 예를 들어 한 스크린의 왼쪽 절반과 다른 스크린의 오른쪽 절반을 본다면 100%를 보는 것이고, 두 스크린의 왼쪽 절반만 본다면 50%만 보는 것입니다.

스크린은 앞면에서만 읽을 수 있습니다. 각 스크린은 왼쪽 끝에서 오른쪽 끝으로 향하는 방향을 가지며, 뒤에서 보면(오른쪽이 내 왼쪽에 오도록 보이면) 그 내용은 전혀 보이지 않습니다.

그림에서 굵은 선은 강의실의 벽입니다. 화살표는 스크린이며 왼쪽에서 오른쪽 방향을 가리킵니다. 회색 영역은 시야 범위이고, 시야가 화살표와 만나는 부분이 그 스크린에서 볼 수 있는 영역입니다. 사람 아래쪽 스크린은 방향이 반대여서 보이지 않습니다. 이 예시에서는 내용의 90%(가장 왼쪽 10%를 제외한 전부)를 볼 수 있습니다.

첫 줄에 데이터 집합의 개수 $K \ge 1$이 주어집니다. 이어서 다음 형식의 데이터 집합이 $K$개 주어집니다.

각 데이터 집합의 첫 줄에는 $n$, $m$, $x$, $y$가 주어집니다. $3 \le n \le 100$은 다각형의 꼭짓점 개수, $1 \le m \le 20$은 스크린의 개수, $(x, y)$는 내 좌석 위치입니다($x$와 $y$는 실수).

다음 $n$개의 줄에는 각각 두 실수 $x_i$, $y_i$가 주어지며, 강의실의 $i$번째 꼭짓점입니다. 모든 $i$에 대해 $(x_i, y_i)$에서 $(x_{i+1}, y_{i+1})$로 벽이 있고, $(x_n, y_n)$에서 $(x_1, y_1)$로도 벽이 있습니다.

이어지는 $m$개의 줄에는 각각 네 실수 $\ell x_j$, $\ell y_j$, $rx_j$, $ry_j$가 주어지며, $j$번째 스크린의 왼쪽 끝점 $(\ell x_j, \ell y_j)$과 오른쪽 끝점 $(rx_j, ry_j)$의 좌표입니다.

각 데이터 집합마다 먼저 "Data Set x:"를 한 줄에 출력합니다($x$는 1부터 시작하는 집합 번호). 그다음 볼 수 있는 내용의 비율을 소수점 아래 둘째 자리까지 반올림하여 출력하고, 끝에 퍼센트 기호(%)를 붙입니다.