Задача 5. Танковый симулятор ≡

Условие

Вася создаёт игру про танки. В игре есть мины, которые имеют форму круга. Танк имеет форму выпуклого многоугольника. Вася хочет придумать механику взаимодействия мины и танка, для этого ему требуется вычислить площадь пересечения мины и танка. Так как у Васи плохо с геометрией, он просит вас написать программу для вычисления площади пересечения танка, заданного координатами вершин, и мины, заданной радиусом и координатами центра.

Формат входного файла

Первая строка входных данных содержит 3 целых числа x_c, y_c, r_c — координаты и радиус мины. Вторая строка содержит одно целое число N — количество вершин в многоугольнике, описывающем танк. Следующие N строк содержат N пар целых чисел (x_i, y_i) (по одной паре в строке) — координаты вершин выпуклого многоугольника, описывающего танк, в порядке обхода по часовой стрелке.

Формат выходного файла

Выходные должны содержать одно вещественное число — площадь пересечения мины и танка с точностью не менее двух знаков после запятой.

Ограничения

−1000 ≤ x_c, y_c, r_c, x_i, y_i ≤ 1000

3 ≤ N ≤ 10³

Описание подзадач и системы оценивания

Решения, работающие для −10 ≤ x_c, y_c, r_c, x_i, y_i ≤ 10, оцениваются из 50 баллов. Баллы выставляются за каждый успешно пройденный тест.

Примеры тестов

1 1 1
4
0 0 0 1 1 1 1 0

0.785398163

0 0 1
3
0 0
0 1
1 0

0.5

0 0 4
4
0 0
0 2
4 4
2 0

7.07035