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

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

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

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

Первая строка входных данных содержит 3 целых числа xc, yc, rc — координаты и радиус мины. Вторая строка содержит одно целое число N — количество вершин в многоугольнике, описывающем танк. Следующие N строк содержат N пар целых чисел (xi, yi) (по одной паре в строке) — координаты вершин выпуклого многоугольника, описывающего танк, в порядке обхода по часовой стрелке.

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

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

Ограничения

1000 ≤ xc, yc, rc, xi, yi ≤ 1000

3 ≤ N ≤ 103

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

Решения, работающие для 10 ≤ xc, yc, rc, xi, yi ≤ 10, оцениваются из 50 баллов. Баллы выставляются за каждый успешно пройденный тест.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1 1
4
0 0 0 1 1 1 1 0
0.785398163
2
0 0 1
3
0 0
0 1
1 0
0.5
3
0 0 4
4
0 0
0 2
4 4
2 0
7.07035

0.168s 0.027s 19