Statements

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

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

Сначала записано число N — количество вершин многоугольника (3 ≤ N ≤ 100), затем N пар вещественных чисел, задающих координаты его вершин.

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

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

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

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

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

11.0

Примечание

Если выводить вещественные числа как print(x), то иногда они будут странно отформатированы, например, $\text{[math]}$ будет выведено как 1e-6.

Поэтому числа с заданной точностью следует переводить в строку так:


x = 1.34
"{:.6f}".format(x)  # строка "1.340000"

Для того, чтобы избежать проблем с погрешностью вашего ответа, если уловие это позволяет, следует выводить числа с максимально возможной точностью, для типа float в Питоне это 16 десятичных знаков:


print("{:.16f}".format(x))

Задан выпуклый многоугольник и точка. Нужно определить, лежит ли точка внутри этого многоугольника.

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

Задано число N (3 ≤ N ≤ 100). Далее идет N пар вещественных чисел, задающих координаты вершин многоугольника. Последние два вещественных числа задают координаты точки. Гарантируется, что точка не лежит на границе многоугольника.

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

В выходной файл выведите сообщение YES, если точка лежит внутри многоугольника или NO, вне него.

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

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

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

NO

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

То, что это прямоугольник, докажите самостоятельно.

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

В первой строке входного файла указано число N (1 ≤ N ≤ 1500). В следующих N строках заданы по 4 целых числа x₁, y₁, x₂, y₂ — сначала координаты левого нижнего угла прямоугольника, потом правого верхнего ( - 10⁹ ≤ x₁ ≤ x₂ ≤ 10⁹, - 10⁹ ≤ y₁ ≤ y₂ ≤ 10⁹). Обратите внимание, что прямоугольники могут вырождаться в отрезки и даже в точки.

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

В единственную строку выходного файла поместите описание искомого прямоугольника в том же формате, в котором заданы прямоугольники во входном файле.

Если пересечение заданных прямоугольников пусто, выведите в выходной файл единственное число -1.

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

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

2
0 0 2 2
1 1 3 3

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

1 1 2 2

Дизайнер Вадим как никогда близок к завершению своего грандиозного проекта — оформлению главной площади города!

Главная площадь представляет собой прямоугольник шириной W и длиной H метров. Вадим задумал покрасить некоторые из квадратов 1x1 метр в зелёный цвет. Для осуществления этого проекта уже заказано N специальных роботов. Роботы умеют перемещаться в соседние по горизонтали, вертикали и диагонали квадраты, и красят все квадраты, в которых побывали. Роботы очень маленькие, поэтому они не сталкиваются друг с другом, даже если красят один квадрат.

Уже почти всё готово к началу работ и Вадим уже написал программу для роботов, состоящую из M команд. Но перед её запуском он хочет убедиться, что в результате получит именно то изображение, которое задумал. Помогите Вадиму!

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

В первой строке записаны 4 числа: W, H, N, M. В каждой из последующих N строк находятся по два целых числа x_i и y_i (0 ≤ x_i < W, 0 ≤ y_i < H) — начальные координаты роботов. В каждой из следующих M строк записана одна из следующих команд для одного из роботов:

left i k — i-ый робот должен k раз повернуть налево на $\text{[math]}$ (0 ≤ i < N, 0 < k ≤ 100)
right i k — i-ый робот должен k раз повернуть направо на $\text{[math]}$ (0 ≤ i < N, 0 < k ≤ 100)
forward i d — i-ый робот должен сделать вперёд d шагов (0 ≤ i < N, d > 0)

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

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

В каждой из H строк выведите по W символов — "#", если в соответствующей клетке побывал хотя бы один из роботов, и "." иначе. Клетке с координатами (0, 0) соответствует левый нижний угол.

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

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

10 7 3 10
3 4
6 5
8 2
left 0 2
forward 0 1
right 1 2
forward 1 1
right 2 3
forward 2 1
right 2 1
forward 2 5
left 2 31
forward 2 1

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

..........
...#..#...
...#..#...
..........
.#......#.
..######..
..........

На плоскости задано N прямоугольников с вершинами в точках с целыми координатами и сторонами, параллельными осям координат. Необходимо найти площадь их объединения.

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

В первой строке входного файла указано число N (1 ≤ N ≤ 1500). В следующих N строках заданы по 4 целых числа x₁, y₁, x₂, y₂ — сначала координаты левого нижнего угла прямоугольника, потом правого верхнего ( - 100 ≤ x₁ ≤ x₂ ≤ 100, - 100 ≤ y₁ ≤ y₂ ≤ 100). Обратите внимание, что прямоугольники могут вырождаться в отрезки и даже в точки.

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

В выходной файл выведите площадь объединения прямоугольников.

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

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

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

На плоскости задано N прямоугольников с вершинами в точках с целыми координатами и сторонами, параллельными осям координат. Необходимо найти площадь их объединения.

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

В первой строке входного файла указано число N (0 ≤ N ≤ 300). В следующих N строках заданы по 4 целых числа x₁, y₁, x₂, y₂ — сначала координаты левого нижнего угла прямоугольника, потом правого верхнего (0 ≤ x₁ ≤ x₂ ≤ 10⁹, 0 ≤ y₁ ≤ y₂ ≤ 10⁹). Обратите внимание, что прямоугольники могут вырождаться в отрезки и даже в точки.

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

В выходной файл выведите единственное число — ответ на задачу.

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

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

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