eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Швабра

Швабра

Першокурсник Рома приїхав у гуртожиток і, здивувавшись безладу у кімнаті та товстому шару пилу на підлозі, пачаі наводить порядок. Перш за все він вирішив вимити підлогу. Для цього Рома у крамниці придбав інноваційну швабру. На момент покупки миюча частина швабри мала ідеальну прямокутну форму, але у процесі перевезення від крамниці до гуртожитку у неї відламався один з кутів. Таким чином, тепер вона являє собою многокутник, границя якого складається з двох сусідніх сторін прямокутника, фрагментів двох сторін, що залишились, і ламаної, яка з'єднує кінці цих фрагментів. \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\}}.
Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB
Вхідні дані #1
9 7
9
3 7
4 5
5 6
4 4
5 2
6 4
7 2
8 3
9 2
Вихідні дані #1
18.0
Джерело XIII Всеросійська командна олімпіада школярів з програмування