eolymp
bolt
Try our new interface for solving problems
Problems

Швабра

Швабра

Первокурсник Рома приехал в общежитие и, удивившись беспорядку в комнате и толстому слою пыли на полу, начал наводить порядок. Первым делом он решил вымыть пол. Для этого Рома в магазине приобрел инновационную швабру. Изначально моющая часть швабры имела идеальную прямоугольную форму, но в процессе перевозки из магазина в общежитие у нее отломился один из углов. Таким образом, теперь она представляет собой многоугольник, граница которого состоит из двух соседних сторон прямоугольника, фрагментов двух оставшихся сторон и ломаной, соединяющей концы этих фрагментов. \includegraphics{https://static.e-olymp.com/content/6b/6bf879d82d490808be4535cb1c5a184fdb8e2e40.jpg} Рома живет в большой прямоугольной комнате. Рома провел сломанной шваброй от одной стороны комнаты до другой, не отрывая ее от стены, так что в результате отломанный угол швабры оказался в углу комнаты. При этом часть соответствующей прямоугольной полосы пола в углу осталась невымытой. \includegraphics{https://static.e-olymp.com/content/02/02c1420dec3d903c9ca8876ea47d7164139a523d.jpg} Рома считает, что все точки, в которых в какой-то момент находилась моющая часть швабры оказались вымыты. Теперь он решил выяснить, какая часть этой полосы осталась грязной. \includegraphics{https://static.e-olymp.com/content/a2/a297c1e4d4d77b0900a118c047e2678ed1c91639.jpg} Помогите ему вычислить площадь этой части. Можете считать, что размер комнаты, в которой живет Рома, существенно больше размеров моющей части швабры. \InputFile Первая строка входного файла содержит два целых числа \textbf{w} и \textbf{h} --- размеры моющей части швабры до повреждения (\textbf{2} ≤ \textbf{w}, \textbf{h} ≤ \textbf{10^5}). Вторая строка содержит целое число \textbf{n} --- число вершин ломаной, соединяющей соседние стороны швабры (\textbf{2} ≤ \textbf{n} ≤ \textbf{10^5}). В \textbf{i}-й из следующих \textbf{n} строк заданы два целых числа \textbf{x_i} и \textbf{y_i} (\textbf{1} ≤ \textbf{x_i} < \textbf{w}, \textbf{1} ≤ \textbf{y_i} < \textbf{h}, за исключением \textbf{y_1= h}, \textbf{x_n} = \textbf{w}) --- координаты \textbf{i}-й вершины ломаной. Ломаная не имеет самопересечений и самокасаний. Координаты введены таким образом, что стена, вдоль которой Рома провел шваброй, соответствует прямой \textbf{y = h}. \OutputFile В выходной файл выведите площадь невымытой части пола с абсолютной или относительной погрешностью не более \textbf{10^\{−6\}}. Это значит, что если правильный ответ \textbf{a}, а вы вывели \textbf{p}, то ваш ответ будет засчитан как правильный, если \textbf{|a−p|/max(|a|,1)} ≤ \textbf{10^\{−6\}}.
Time limit 2 seconds
Memory limit 256 MiB
Input example #1
9 7
9
3 7
4 5
5 6
4 4
5 2
6 4
7 2
8 3
9 2
Output example #1
18.0
Source XIII All-Russian Olympiad schoolchildren team programming