Розв`язання задачі про забруднення
Будучи співробітником підрозідлу природокористування та охорони навколишнього середовища, ви повинні слідкувати за відходами, які скидуються (інколи випадково, інколи спеціально) у річки, озера та океани. Одна з ваших задач — вимірювання впливу забруднення на різні водні екосистеми, такі як коралові рифи, місця нересту і так далі.
Рисунок: Ілюстрація до прикладу 1.
Модель, яку ви використовуєте при аналізі, зображена на рисунку. Берегова лінія (горизонтальна лінія на рисунку) лежить на осі x, джерело забруднення розміщено у початку координат (0, 0). Розповсюдження забруднення у воду подано півкругом, а многокутник позначає екосистему, яка вас цікавить. Вам потрібно визначити площу екосистеми, яка була забруднена, тобто площу темно-синьої області на рисунку.
Вхідні дані
Вхідні дані містять один набір тестів. Тест починається рядоком, який містить два цілих числа n та r, де n (3 ≤ n ≤ 100) - це кількість вершин многокутника, r (1 ≤ r ≤ 1000) - це радіус поля забруднення. Далі йдуть n рядків, кожен з яких містить по два цілих числа x_i та y_i - координати вершин многокутника у порядку проти годинникової стрілки, причому -1500 ≤ x_i ≤ 1500 та 0 ≤ y_i ≤ 1500. Многокутник не має самоперетинів та самодотикань. Ніяка вершина не лежить на колі.
Вихідні дані
Виведіть площу частини многокутника, яка попадає у півкруг з центром у початку координат радіуса r. Дайте відповідь з абсолютною похибкою не більше 10^{−3}.