Страница: << 1 2 3 4 5 6 7 Отображать по:

#111828

Швабра

Темы: [Вычислительная геометрия]

Источники: [ Командные олимпиады, ВКОШП, 2012, Задача J ]

Первокурсник Рома приехал в общежитие и, удивившись беспорядку в комнате и толстому слою пыли на полу, начал наводить порядок. Первым делом он решил вымыть пол. Для этого Рома в магазине приобрел инновационную швабру.

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

$\text{[math]}$

Рома живет в большой прямоугольной комнате. Рома провел сломанной шваброй от одной стороны комнаты до другой, не отрывая ее от стены, так что в результате отломанный угол швабры оказался в углу комнаты. При этом часть соответствующей прямоугольной полосы пола в углу осталась невымытой.

$\text{[math]}$

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

$\text{[math]}$

Помогите ему вычислить площадь этой части. Можете считать, что размер комнаты, в которой живет Рома, существенно больше размеров моющей части швабры.

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

Первая строка входного файла содержит два целых числа $w$ и $h$ - размеры моющей части швабры до повреждения ($2 \le w, h \le 10^5$).

Вторая строка содержит целое число $n$ - число вершин ломаной, соединяющей соседние стороны швабры ($2 \le n \le 10^5$). В $i$-й из следующих $n$ строк заданы два целых числа $x_i$ и $y_i$ ($1 \le x_i < w$, $1 \le y_i < h$, за исключением $y_1 = h$, $x_n = w$) - координаты $i$-й вершины ломаной. Ломаная не имеет самопересечений и самокасаний.

Координаты введены таким образом, что стена, вдоль которой Рома провел шваброй, соответствует прямой $y=h$.

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

В выходной файл выведите площадь невымытой части пола с абсолютной или относительной погрешностью не более $10^{-6}$. Это значит, что если правильный ответ $a$, а вы вывели $p$, то ваш ответ будет засчитан как правильный, если $\frac{|a-p|}{\max(|a|, 1)}\le 10^{-6}$.

Примеры

Входные данные

Выходные данные

18.0

Страница: << 1 2 3 4 5 6 7 Отображать по:

Выбрано

Отменить

Добавить в контест