시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB89922813722.948%

문제

두 개의 볼록 다각형이 주어진다. 두 볼록 다각형의 넓이는 0이 아니다. 그리고, 볼록 다각형 1의 꼭짓점은 볼록 다각형2의 변 위에 있지 않고, 그 반대도 마찬가지이다.

이때, 두 볼록 다각형의 겹쳐진 부분의 넓이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 볼록 다각형1의 꼭짓점의 개수 N, 볼록 다각형2의 꼭짓점의 개수 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 볼록 다각형1의 꼭짓점이 반시계 방향 순서대로 주어지고, 다음 줄부터 M개의 줄에는 볼록 다각형2의 꼭짓점이 반시계 방향 순서대로 주어진다. 각 좌표의 절댓값은 1,000보다 작거나 같은 정수이다. 그리고 각 볼록 다각형의 넓이는 0이 아니다.

출력

첫째 줄에 두 다각형의 겹친 부분의 넓이를 출력한다. 절대/상대 오차는 10-9까지 허용한다.

예제 입력 1

3 4
0 0
2 0
0 3
1 1
3 1
3 3
1 3

예제 출력 1

0.08333333333333326

예제 입력 2

4 8
-1 -1
1 -1
1 1
-1 1
-2 -2
0 -2
2 -2
2 0
2 2
0 2
-2 2
-2 0

예제 출력 2

4.0

예제 입력 3

3 3
-1 -1
-2 -1
-1 -2
1 1
2 1
1 2

예제 출력 3

0.0

예제 입력 4

6 4
-2 0
-1 -2
1 -2
2 0
1 2
-1 2
0 -3
1 -1
2 2
-1 0

예제 출력 4

5.233333333333333

출처