Задача C. Морской бой ≡

Условие

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

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

Первая строка входных данных содержит 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