시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 140 27 18 19.780%

문제

두 개의 볼록 다각형이 주어진다. 두 볼록 다각형의 넓이는 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

출처