Задача A. Приземление ≡

Условие

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

Площадка представляет собой прямоугольник со сторонами, параллельными осям координат. Корабль (вид сверху) — выпуклый многоугольник.

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

Вычислите площадь той части площадки космодрома, все точки которой будут в безопасности при любом случае посадки, не нарушающем указанные выше правила.

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

В первой строке входного файла находятся 4 целых числа: N (количество вершин многоугольника, описывающего корабль), W, H (размеры площадки) и d (безопасное расстояние). Затем следует N пар целых чисел X_i Y_i через пробел, по одной паре в каждой строке — координаты планируемого положения корабля, заданные в порядке обхода. Последовательные точки в порядке обхода границы многоугольника могут лежать на одной прямой и даже совпадать.

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

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

Ограничения

3 ≤ N ≤ 100

0 ≤ W, H ≤ 10⁴

0 ≤ X_i ≤ W

0 ≤ Y_i ≤ H

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

3 100 100 1
10 10
20 10
10 20

56.7162717227

Задача B. Минимальная площадь ≡

Условие

Примечание. Формат данной задачи не поддерживается в CATS. Предоставляется лишь текст условия для ознакомления. Ограничение по времени игнорировать. Подразумевается, что полученная программа должна завершить работу втечение пятичасового тура.

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

Оценка за решение — это сумма оценок за каждый тест, округленная до ближайшего целого числа. Оценка за отдельный тест вычисляется следующим образом. Каждому тесту T соответствует максимальное количество баллов B_T, которое можно за него получить. Если ответ на тесте некорректен, оценка равна нулю. В противном случае оценка — это L/M ⋅ B_T, где L — это минимальная площадь треугольника в конфигурации, полученной участником, а M — это максимальная изо всех минимальных площадей, полученных всеми участниками и жюри за всю олимпиаду на этом тесте. В частности, если участник расставил точки так, что L является максимальной площадью, которую удалось получить на этом тесте, оценка за тест T будет равна B_T. Максимальные баллы за каждый тест одинаковы. Сумма максимальных баллов по всем тестам равна 100.

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

В первой и единственной строке каждого входного файла записано целое число n — количество точек.

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

Выведите в каждый выходной файл n строк, где n — число из соответствующего входного файла. В каждой строке выведите координаты i-ой точки x_i и y_i через пробел. Точки должны лежать внутри или на границе единичного квадрата, то есть их координаты должны удовлетворять соотношениям 0 ≤ x_i ≤ 1, 0 ≤ y_i ≤ 1. Порядок точек не имеет значения.

Координаты и площади обрабатываются проверяющей программой как числа с плавающей точкой двойной точности (тип double в языках C/C++ и Pascal).

Ограничения

3 ≤ n ≤ 52

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

4

0.000000000000 0.000000000000
0.000000000000 1.000000000000
0.800000000000 0.300000000000
0.300000000000 0.800000000000

Задача C. Цветная полоска ≡

Условие

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

Более точно: полоска условно делится на квадраты размера 1 × 1 сантиметр. В начале центр первого квадрата фиксируется на столе. На i-м шаге от центра последнего зафиксированного квадрата отступают K_i сантиметров и фиксируют там центр соответствующего квадрата. Затем полоску сгибают в этом месте так, чтобы на месте квадрата, где находится сгиб, образовался прямоугольный треугольник. Полоска сгибается через верх, то есть цвет i-го треугольника не совпадает с цветом i-го отрезка. Затем переходят к следующему шагу.

Сначала полоска выкладывается зеленой стороной вверх.

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

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

Ограничения

1 ≤ N ≤ 100

Все K_i целые, 1 ≤ K_i ≤ 10⁷.

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

1
10 1

10.00
0.50

2
10 1
20 2

10.50
19.50