Решение задачи о загрязнении
Будучи сотрудником отделения природопользования и охраны окружающей среды, вы должны следить за отходами, которые сбрасываются (иногда случайно, иногда специально) в реки, озёра и океаны. Одна из ваших задач — измерение влияния загрязнения на различные водные экосистемы, такие как коралловые рифы, места нереста и так далее.
Рисунок: Иллюстрация к примеру 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}.