시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 30 8 6 46.154%

문제

수질 오염 관리 본부 직원인 해빈이는 강, 호수, 바다로 배출되는 오염 물질을 모니터링 하는 작업을 맡고 있다. 해빈이의 업무는 산호초, 산란지 등이 수질 생태계에 미치는 영향을 측정하는 것이다.

그림 1: 예제 입력에 대한 그림

해빈이가 분석에 사용하는 모델은 그림 1에 도식화되어 있다. 해안가(shoreline) 는 x축에 놓여 있고 오염의 근원지인 Source는 (0,0)에 위치해 있다. 반원은 오염이 퍼지는 경로를 나타내고 다각형은 오염이 우려되는 생태계를 나타낸다. 해빈이는 도표에 표시된 것 처럼 생태계와 오염지역이 겹치는 파란색 영역의 넓이를 구해야 한다.

입력

첫째 줄에 n, r 두개의 정수가 입력으로 주어진다 (3 ≤ n ≤ 100, 1 ≤ r ≤ 1,000). n은 생태계를 나타내는 다각형의 꼭지점의 개수이고 r은 source로 부터의 반지름을 나타 낸다. 뒤이어 n개의 줄에 각각 다각형의 꼭지점의 좌표를 나타내는 두 정수 xi, yi가 반시계 방향으로 주어진다 (-1,500 ≤ xi ≤ 1,500 and 0 ≤ yi ≤ 1,500).다각형은 서로 교차하거나 만나지 않고 꼭지점이 반원의 경계에 놓인 경우도 없다.

출력

원점을 중심으로 반지름 r 의 반원에 포함된 다각형의 넓이를 출력한다. 정답과의 차이가 10-3이하면 정답으로 인정한다.

예제 입력

6 10
-8 2
8 2
8 14
0 14
0 6
-8 14

예제 출력

101.576437872

힌트

출처

ACM-ICPC > World Finals > 2013 World Finals J번

  • 문제를 번역한 사람: lll4592