시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 40 12 10 43.478%

문제

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

그림 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이하면 정답으로 인정한다.

예제 입력 1

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

예제 출력 1

101.576437872
W3sicHJvYmxlbV9pZCI6Ijg4ODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2MjRcdWM1ZmMgXHVkNTc0XHVhY2IwXHVjYzQ1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyMThcdWM5YzggXHVjNjI0XHVjNWZjIFx1YWQwMFx1YjlhYyBcdWJjZjhcdWJkODAgXHVjOWMxXHVjNmQwXHVjNzc4IFx1ZDU3NFx1YmU0OFx1Yzc3NFx1YjI5NCBcdWFjMTUsIFx1ZDYzOFx1YzIxOCwgXHViYzE0XHViMmU0XHViODVjIFx1YmMzMFx1Y2Q5Y1x1YjQxOFx1YjI5NCBcdWM2MjRcdWM1ZmMgXHViYjNjXHVjOWM4XHVjNzQ0IFx1YmFhOFx1YjJjOFx1ZDEzMFx1YjljMSBcdWQ1NThcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YjllMVx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1ZDU3NFx1YmU0OFx1Yzc3NFx1Yzc1OCBcdWM1YzVcdWJiMzRcdWIyOTQgXHVjMGIwXHVkNjM4XHVjZDA4LCBcdWMwYjBcdWI3ODBcdWM5YzAgXHViNGYxXHVjNzc0IFx1YzIxOFx1YzljOCBcdWMwZGRcdWQwZGNcdWFjYzRcdWM1ZDAgXHViYmY4XHVjZTU4XHViMjk0IFx1YzYwMVx1ZDVhNVx1Yzc0NCBcdWNlMjFcdWM4MTVcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BvbGwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjAzcHg7IHdpZHRoOjM4NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjliYyAxOiBcdWM2MDhcdWM4MWMgXHVjNzg1XHViODI1XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWFkZjhcdWI5YmM8XC9wPlxyXG5cclxuPHA+XHVkNTc0XHViZTQ4XHVjNzc0XHVhYzAwIFx1YmQ4NFx1YzExZFx1YzVkMCBcdWMwYWNcdWM2YTlcdWQ1NThcdWIyOTQgXHViYWE4XHViMzc4XHVjNzQwIFx1YWRmOFx1YjliYyAxXHVjNWQwIFx1YjNjNFx1YzJkZFx1ZDY1NFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1ZDU3NFx1YzU0OFx1YWMwMChzaG9yZWxpbmUpIFx1YjI5NCB4XHVjZDk1XHVjNWQwIFx1YjE5M1x1YzVlYyBcdWM3ODhcdWFjZTAgXHVjNjI0XHVjNWZjXHVjNzU4IFx1YWRmY1x1YzZkMFx1YzljMFx1Yzc3OCBTb3VyY2VcdWIyOTQgKDAsMClcdWM1ZDAgXHVjNzA0XHVjZTU4XHVkNTc0IFx1Yzc4OFx1YjJlNC4gXHViYzE4XHVjNmQwXHVjNzQwIFx1YzYyNFx1YzVmY1x1Yzc3NCBcdWQzN2NcdWM5YzBcdWIyOTQgXHVhY2JkXHViODVjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWNlMCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NDAgXHVjNjI0XHVjNWZjXHVjNzc0IFx1YzZiMFx1YjgyNFx1YjQxOFx1YjI5NCBcdWMwZGRcdWQwZGNcdWFjYzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWQ1NzRcdWJlNDhcdWM3NzRcdWIyOTQgXHViM2M0XHVkNDVjXHVjNWQwIFx1ZDQ1Y1x1YzJkY1x1YjQxYyBcdWFjODMgXHVjYzk4XHViN2ZjIFx1YzBkZFx1ZDBkY1x1YWNjNFx1YzY0MCBcdWM2MjRcdWM1ZmNcdWM5YzBcdWM1ZWRcdWM3NzQgXHVhY2I5XHVjZTU4XHViMjk0IFx1ZDMwY1x1Yjc4MFx1YzBjOSBcdWM2MDFcdWM1ZWRcdWM3NTggXHViMTEzXHVjNzc0XHViOTdjIFx1YWQ2Y1x1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIG4sIHIgXHViNDUwXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0ICgzICZsZTsgbiAmbGU7IDEwMCwgMSAmbGU7IHIgJmxlOyAxLDAwMCkuIG5cdWM3NDAgXHVjMGRkXHVkMGRjXHVhY2M0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHVhZjJkXHVjOWMwXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YWNlMCByXHVjNzQwIHNvdXJjZVx1Yjg1YyBcdWJkODBcdWQxMzBcdWM3NTggXHViYzE4XHVjOWMwXHViOTg0XHVjNzQ0IFx1YjA5OFx1ZDBjMCBcdWIwYjhcdWIyZTQuIFx1YjRhNFx1Yzc3NFx1YzViNCBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjMDFcdWFjMDEgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YWYyZFx1YzljMFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMTggeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YmMxOFx1YzJkY1x1YWNjNCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0ICgtMSw1MDAgJmxlOyB4PHN1Yj5pPFwvc3ViPiAmbGU7IDEsNTAwIGFuZCAwICZsZTsgeTxzdWI+aTxcL3N1Yj4gJmxlOyAxLDUwMCkuXHViMmU0XHVhYzAxXHVkNjE1XHVjNzQwIFx1YzExY1x1Yjg1YyBcdWFkNTBcdWNjMjhcdWQ1NThcdWFjNzBcdWIwOTggXHViOWNjXHViMDk4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWFmMmRcdWM5YzBcdWM4MTBcdWM3NzQgXHViYzE4XHVjNmQwXHVjNzU4IFx1YWNiZFx1YWNjNFx1YzVkMCBcdWIxOTNcdWM3NzggXHVhY2JkXHVjNmIwXHViM2M0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM2ZDBcdWM4MTBcdWM3NDQgXHVjOTExXHVjMmVjXHVjNzNjXHViODVjIFx1YmMxOFx1YzljMFx1Yjk4NCByIFx1Yzc1OCBcdWJjMThcdWM2ZDBcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDFjIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc1OCBcdWIxMTNcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM4MTVcdWIyZjVcdWFjZmNcdWM3NTggXHVjYzI4XHVjNzc0XHVhYzAwIDEwPHN1cD4tMzxcL3N1cD5cdWM3NzRcdWQ1NThcdWJhNzQgXHVjODE1XHViMmY1XHVjNzNjXHViODVjIFx1Yzc3OFx1YzgxNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI4ODg2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUG9sbHV0aW9uIFNvbHV0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5BcyBhbiBlbXBsb3llZSBvZiBBcXVlb3VzIENvbnRhbWluYXRlIE1hbmFnZW1lbnQsIHlvdSBtdXN0IG1vbml0b3IgdGhlIHBvbGx1dGlvbiB0aGF0IGdldHMgZHVtcGVkIChzb21ldGltZXMgYWNjaWRlbnRhbGx5LCBzb21ldGltZXMgcHVycG9zZWZ1bGx5KSBpbnRvIHJpdmVycywgbGFrZXMgYW5kIG9jZWFucy4gT25lIG9mIHlvdXIgam9icyBpcyB0byBtZWFzdXJlIHRoZSBpbXBhY3Qgb2YgdGhlIHBvbGx1dGlvbiBvbiB2YXJpb3VzIGVjb3N5c3RlbXMgaW4gdGhlIHdhdGVyIHN1Y2ggYXMgY29yYWwgcmVlZnMsIHNwYXduaW5nIGdyb3VuZHMsIGFuZCBzbyBvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wb2xsLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwM3B4OyB3aWR0aDozODRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgSi4xOiBJbGx1c3RyYXRpb24gb2YgU2FtcGxlIElucHV0LjxcL3A+XHJcblxyXG48cD5UaGUgbW9kZWwgeW91IHVzZSBpbiB5b3VyIGFuYWx5c2lzIGlzIGlsbHVzdHJhdGVkIGluIEZpZ3VyZSBKLjEuIFRoZSBzaG9yZWxpbmUgKHRoZSBob3Jpem9udGFsIGxpbmUgaW4gdGhlIFx1ZmIwMWd1cmUpIGxpZXMgb24gdGhlIHgtYXhpcyB3aXRoIHRoZSBzb3VyY2Ugb2YgdGhlIHBvbGx1dGlvbiBsb2NhdGVkIGF0IHRoZSBvcmlnaW4gKDAsMCkuIFRoZSBzcHJlYWQgb2YgdGhlIHBvbGx1dGlvbiBpbnRvIHRoZSB3YXRlciBpcyByZXByZXNlbnRlZCBieSB0aGUgc2VtaWNpcmNsZSwgYW5kIHRoZSBwb2x5Z29uIHJlcHJlc2VudHMgdGhlIGVjb3N5c3RlbSBvZiBjb25jZXJuLiBZb3UgbXVzdCBkZXRlcm1pbmUgdGhlIGFyZWEgb2YgdGhlIGVjb3N5c3RlbSB0aGF0IGlzIGNvbnRhbWluYXRlZCwgcmVwcmVzZW50ZWQgYnkgdGhlIGRhcmsgYmx1ZSByZWdpb24gaW4gdGhlIFx1ZmIwMWd1cmUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgYSBzaW5nbGUgdGVzdCBjYXNlLiBBIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0d28gaW50ZWdlcnMgbiBhbmQgciwgd2hlcmUgMyAmbGU7IG4gJmxlOyAxMDAgaXMgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyBpbiB0aGUgcG9seWdvbiBhbmQgMSAmbGU7IHIgJmxlOyAxIDAwMCBpcyB0aGUgcmFkaXVzIG9mIHRoZSBwb2xsdXRpb24gXHVmYjAxZWxkLiBUaGlzIGlzIGZvbGxvd2VkIGJ5IG4gbGluZXMsIGVhY2ggY29udGFpbmluZyB0d28gaW50ZWdlcnMgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+LCBnaXZpbmcgdGhlIGNvb3JkaW5hdGVzIG9mIHRoZSBwb2x5Z29uIHZlcnRpY2VzIGluIGNvdW50ZXItY2xvY2t3aXNlIG9yZGVyLCB3aGVyZSAtMSA1MDAgJmxlOyB4PHN1Yj5pPFwvc3ViPiAmbGU7IDEgNTAwIGFuZCAwICZsZTsgeTxzdWI+aTxcL3N1Yj4gJmxlOyAxIDUwMC4gVGhlIHBvbHlnb24gZG9lcyBub3Qgc2VsZi1pbnRlcnNlY3Qgb3IgdG91Y2ggaXRzZWxmLiBObyB2ZXJ0ZXggbGllcyBvbiB0aGUgY2lyY2xlIGJvdW5kYXJ5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkRpc3BsYXkgdGhlIGFyZWEgb2YgdGhlIHBvbHlnb24gdGhhdCBmYWxscyB3aXRoaW4gdGhlIHNlbWljaXJjbGUgY2VudGVyZWQgYXQgdGhlIG9yaWdpbiB3aXRoIHJhZGl1cyByLiBHaXZlIHRoZSByZXN1bHQgd2l0aCBhbiBhYnNvbHV0ZSBlcnJvciBvZiBhdCBtb3N0IDEwPHN1cD4tMzxcL3N1cD4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

  • 문제를 번역한 사람: lll4592