| Автор: | Жюри всероссийских зимних сборов школьников 2007-2008 | Ограничение времени: | 2 сек | |
| Входной файл: | landing.in | Ограничение памяти: | 256 Мб | |
| Выходной файл: | landing.out | |||
| Максимальный балл: | 100 |
Космический корабль приземляется на прямоугольную площадку космодрома. Правда, пилот не слишком опытен, поэтому возможны некоторые неточности…
Площадка представляет собой прямоугольник со сторонами, параллельными осям координат. Корабль (вид сверху) — выпуклый многоугольник.
Точка находится в безопасности, если расстояние от нее до корабля не меньше d. Автоматические системы не дадут посадить корабль так, чтобы хоть одна точка вне площадки не оказалась в безопасности. Также эти системы не разрешат вращение корабля в плоскости площадки, однако разрешат его параллельный перенос. Гарантируется, что корабль можно посадить.
Вычислите площадь той части площадки космодрома, все точки которой будут в безопасности при любом случае посадки, не нарушающем указанные выше правила.
В первой строке входного файла находятся 4 целых числа: N (количество вершин многоугольника, описывающего корабль), W, H (размеры площадки) и d (безопасное расстояние). Затем следует N пар целых чисел Xi Yi через пробел, по одной паре в каждой строке — координаты планируемого положения корабля, заданные в порядке обхода. Последовательные точки в порядке обхода границы многоугольника могут лежать на одной прямой и даже совпадать.
Выходной файл должен содержать одно вещественное число с не менее, чем 6 точными знаками после запятой — площадь космодрома, на которой находиться будет безопасно.
3 ≤ N ≤ 100
0 ≤ W, H ≤ 104
0 ≤ Xi ≤ W
0 ≤ Yi ≤ H
| № | Входной файл (landing.in) |
Выходной файл (landing.out) |
|---|---|---|
| 1 | |
|