라디오 방송

시간 제한1초메모리 제한128 MB

요약

원과 단순 다각형이 주어질 때, 다각형 내부이면서 원 안에 들어가는 영역의 넓이를 구한다.

난이도: 어려움10점 중 8점
유형: 기하, 배열
정답자: 아직 제출이 없습니다

문제

한 유명한 라디오 방송국이 새 송신탑을 세우려고 합니다. 설치 위치와 신호 세기가 정해졌고, 이 두 값이 라디오를 수신할 수 있는 영역인 원의 중심과 반지름을 결정합니다. 나라의 국경은 다각형으로 주어집니다. 이 정보를 바탕으로 방송 전파가 나라 안에서 실제로 도달하는 영역의 넓이를 구하세요. 이 넓이는 투자 수익성에 큰 영향을 주므로 중요합니다. 나라의 영토는 평면이라고 가정합니다.

입력

첫 번째 줄에 이어지는 데이터 집합의 개수를 나타내는 작은 정수 $z$ 가 주어집니다. 각 데이터 집합은 다음과 같이 구성됩니다.

첫 번째 줄에는 정수 $x$ , $y$ , $r$ , $n$ 이 주어지며, 각각 방송국의 $x$ 좌표와 $y$ 좌표, 송신 반지름, 국경을 나타내는 다각형의 꼭짓점 개수를 의미합니다 ( $-10^6 \le x, y \le 10^6$ , $0 \le r \le 10^6$ , $3 \le n \le 10^6$ ). 이어지는 $n$ 개의 줄에는 다각형 꼭짓점의 좌표가 한 줄에 하나씩 두 정수 $x$ 와 $y$ 로 주어집니다 ( $-10^6 \le x, y \le 10^6$ ). 꼭짓점은 국경을 따라 나타나는 순서대로 주어지며, 진행 방향(시계 방향인지 반시계 방향인지)은 정해져 있지 않습니다. 국경 다각형은 자기 자신과 교차하지 않습니다. 송신탑은 나라의 국경 밖에 있을 수도 있습니다.

출력

각 데이터 집합마다, 국경 안에서 방송국의 전파가 도달하는 영역의 넓이를 소수점을 포함한 실수로, 소수점 아래 정확히 셋째 자리까지(가장 가까운 1/1000 단위로 반올림하여) 한 줄에 출력하세요.

예제4

예제 1
입력
```
1
0 0 1 3
1 1
1 0
0 1
```
예상 출력
```
0.285
```

예제 2

입력

예상 출력

3.142

예제 3
입력
```
1
100 100 1 3
0 0
5 0
0 5
```
예상 출력
```
0.000
```

예제 4

입력

3
0 0 1 3
1 1
1 0
0 1
0 0 1 4
-10 -10
10 -10
10 10
-10 10
100 100 1 3
0 0
5 0
0 5

예상 출력

0.285
3.142
0.000