Розв'язання задачі про забруднення#5659

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

1 секунда

256 мегабайтів

Дуже складна

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

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

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

Вхідні дані

Вхідні дані містять один набір тестів. Тест починається рядком, який містить два цілих числа $n$ та $r$ , де $n$ ( $3 \leq n \leq 100$ 3 \le n \le 100) - це кількість вершин многокутника, $r$ ( $1 \leq r \leq 1000$ 1 \le r \le 1000) - це радіус поля забруднення. Далі йдуть $n$ рядків, кожен з яких містить по два цілих числа $x_{i}$ x_i та $y_{i}$ y_i - координати вершин многокутника у порядку проти годинникової стрілки, причому $- 1500 \leq x_{i} \leq 1500$ -1500 \le x_i \le 1500 та $0 \leq y_{i} \leq 1500$ 0 \le y_i \le 1500. Многокутник не має самоперетинів та самодотикань. Ніяка вершина не лежить на колі.

Вихідні дані

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

Приклади

Приклад 1