eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Розв`язання задачі про забруднення

Розв`язання задачі про забруднення

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

Будучи співробітником підрозідлу природокористування та охорони навколишнього середовища, ви повинні слідкувати за відходами, які скидуються (інколи випадково, інколи спеціально) у річки, озера та океани. Одна з ваших задач — вимірювання впливу забруднення на різні водні екосистеми, такі як коралові рифи, місця нересту і так далі.

Рисунок: Ілюстрація до прикладу 1.

Модель, яку ви використовуєте при аналізі, зображена на рисунку. Берегова лінія (горизонтальна лінія на рисунку) лежить на осі x, джерело забруднення розміщено у початку координат (0, 0). Розповсюдження забруднення у воду подано півкругом, а многокутник позначає екосистему, яка вас цікавить. Вам потрібно визначити площу екосистеми, яка була забруднена, тобто площу темно-синьої області на рисунку.

Вхідні дані

Вхідні дані містять один набір тестів. Тест починається рядоком, який містить два цілих числа n та r, де n (3n100) - це кількість вершин многокутника, r (1r1000) - це радіус поля забруднення. Далі йдуть n рядків, кожен з яких містить по два цілих числа x_i та y_i - координати вершин многокутника у порядку проти годинникової стрілки, причому -1500x_i1500 та 0y_i1500. Многокутник не має самоперетинів та самодотикань. Ніяка вершина не лежить на колі.

Вихідні дані

Виведіть площу частини многокутника, яка попадає у півкруг з центром у початку координат радіуса r. Дайте відповідь з абсолютною похибкою не більше 10^{−3}.

Приклад

Вхідні дані #1
6 10
-8 2
8 2
8 14
0 14
0 6
-8 14
Вихідні дані #1
101.576437872
Джерело ACM-ICPC World Finals 2013