| 0 | 2 | 2 | 2 | 2 |
| 0 | 2 | 2 | 2 | 2 |
| 1 | 1 | 2 | 2 | 2 |
| 1 | 1 | 0 | 0 | 0 |
На поле NxM клеток (N строк и M столбцов) положили K прямоугольников один поверх другого в случайном порядке. Длины сторон прямоугольников выражаются целым числом клеток. Прямоугольники не выходят за границы поля. Границы прямоугольников совпадают с границами клеток поля.
Получившуюся ситуацию записали в таблицу чисел (каждой клетке поля соответствует клетка таблицы). Если клетка поля не закрыта прямоугольником, то в соответствующую клетку таблицы записали число 0. Если же клетка закрыта одним или несколькими прямоугольниками, то в соответствующую клетку таблицы записали число, соответствующее номеру самого верхнего прямоугольника, закрывающего эту клетку.
По содержимому таблицы требуется определить положение и размеры прямоугольников.
Гарантируется, что во входных данных содержится информация, которой достаточно для однозначного определения размеров прямоугольников.
В первой строке входного файла записаны целые числа N, M, K (1N200, 1M200, 1K255). Далее следует N строк по M чисел в каждой — содержимое таблицы. Все числа в таблице целые, находятся в диапазоне от 0 до K включительно.
В выходной файл необходимо выдать K строк. Каждая строка должна описывать соответствующий ее номеру прямоугольник четырьмя числами R C H W (R и C должны описывать координаты левого нижнего угла прямоугольника, а H и W — координаты правого верхнего угла). Числа должны разделяться пробелом.
4 5 2 0 2 2 2 2 0 2 2 2 2 1 1 2 2 2 1 1 0 0 0
0 0 2 2 1 1 5 4
В пространстве с прямоугольной системой координат находятся два куба. Про них известно следующее:
Требуется найти объем пересечения (т.е. общей части) этих кубов.
Во входном файле записаны 8 троек действительных чисел – координаты вершин второго куба B1B2B3B4B5B6B7B8.
В выходной файл выведите одно число – искомый объем пересечения кубов. Ответ не должен отличаться от верного более чем на 0.00001.
1.0000000000 -1.0000000000 1.0000000000 1.0000000000 -1.0000000000 -1.0000000000 -1.0000000000 -1.0000000000 -1.0000000000 -1.0000000000 -1.0000000000 1.0000000000 1.0000000000 1.0000000000 1.0000000000 1.0000000000 1.0000000000 -1.0000000000 -1.0000000000 1.0000000000 -1.0000000000 -1.0000000000 1.0000000000 1.0000000000
8.00000000000000000000
1.4142135623730950488016887242097 0 1 0 -1.4142135623730950488016887242097 1 -1.4142135623730950488016887242097 0 1 0 1.4142135623730950488016887242097 1 1.4142135623730950488016887242097 0 -1 0 -1.4142135623730950488016887242097 -1 -1.4142135623730950488016887242097 0 -1 0 1.4142135623730950488016887242097 -1
6.62741699796952078000
Муха летит вдоль прямой. Если нанести на эту прямую координаты, то можно сказать, что в 0-й момент времени муха пролетает точку с координатой 0 и летит в положительном направлении со скоростью V. Муха может менять свою скорость, однако ускорение мухи не может по модулю превышать величины A, в частности, муха не может мгновенно остановиться. Максимальная скорость мухи не может превышать по модулю величины W.
Известно, что в момент времени T по прямой ударит мухобойка, которая полностью накроет отрезок от точки C до точки D. Если муха в этот момент окажется на этом отрезке, она погибнет.
Напишите программу, которая определит, есть ли у мухи шанс спастись, и если есть, то выведет, что должна муха для этого делать.
Во входном файле заданы числа V, W, A, T, C, D. Все числа целые. 0≤V≤W≤1000, 0≤A≤1000, 0<T≤1000, –1000000≤C≤D≤1000000.
Если муха может спастись, выведите, как она должна для этого лететь. Для этого выведите последовательность команд для мухи. Количество команд не должно превышать 100. Каждая команда задается двумя числами Ti, Ai, которые обозначают, что в течение времени Ti муха должна лететь с ускорением Ai. Ti и Ai не обязаны быть целыми, Ti должны быть положительны (не могут быть равны 0), сумма всех Ti должна быть равна T с точностью до 10-6.
Если, в рамках указанных ограничений, муха спастись не сможет, в выходной файл выведите одно число –1 (минус 1).
Примечания
Муха может сначала снизить скорость до 0, а затем полететь в обратную сторону (см. примеры).
Если в момент времени T муха окажется на концах отрезка, т.е. в точке C или D, она все равно погибнет.
Комментарии к примерам тестов
1. Муха не сможет спастись.
2. Сначала в течение времени 0.2 муха летит с постоянной скоростью 10, а затем ускоряется с ускорением 4
3. Муха сначала тормозит с ускорением -5, а затем с этим же ускорением начинает лететь в обратную сторону. Набрав скорость 10, муха продолжает лететь с ней без ускорения.
10 10 5 1 -100 100
-1
10 20 5 1 9 11
1 5
10 10 5 5 0 1000
4.000000000000000000 -5 1.000000000000000000 0
На плоскости дано N горизонтальных отрезков. Будем говорить, что прямая пересекает отрезок, если у этой прямой и этого отрезка есть хотя бы одна общая точка (в том числе прямая пересекает отрезок, если она проходит через один из его концов). Требуется найти прямую, пересекающую все отрезки, или установить, что такой нет.>
В первой строке входного файла находится единственное число N. В каждой из следующих N строк содержатся по три целых числа Pi, Qi, Ri, описывающих отрезки: соответствующий отрезок соединяет точки (Pi, Ri) и (Qi, Ri). Никакие два отрезка не лежат на одной прямой.
1≤N≤10000, Pi<Qi, все числа по модулю не превосходят 10000.
В случае, если искомая прямая существует, выведите в выходной файл коэффициенты ее уравнения (будем задавать прямую уравнением вида A∙x+B∙y+C=0, где x, y – координаты точек прямой, A, B, C – такие коэффициенты, что указанному уравнению удовлетворяют все точки прямой, и только они; соответственно, чтобы задать прямую, нужно задать три числа – A, B, C).
Коэффициенты уравнения должны быть целыми и не должны превосходить по модулю 109 (гарантируется, что при наличии решения такие A, B, C существуют).
Если прямой не существует, выведите в выходной файл сообщение “No solution” (без кавычек).
3 0 1 0 0 1 1 0 1 2
1 0 0
5 0 2 0 2 4 1 1 3 2 1 3 -1 1 3 -2
3 -1 -5
3 0 1 0 1 2 1 -2 -1 2
No solution
С незапамятных времен граница страны Флатландия имеет форму N-угольника без самопересечений и самокасаний (необязательно выпуклого). В каждой из вершин этого многоугольника король построил по башне.
В целях увеличения обороноспособности государства на его территории король задумал построить Великий Флатландский Забор. По причине многолетней войны ресурсов хватает на строительство ровно K стен (неважно, какой длины). Каждая стена должна соединять ровно две башни по прямой и не должна даже частично выходить за пределы Флатландии. К тому же, Забор должен представлять собой не более чем K-угольник также без самопересечений и самокасаний (углов может оказаться и меньше, чем K, так как некоторые соседние стены могут лежать на одной прямой). Военный советник настаивает на том, что площадь защищенной области должна быть как можно больше.
Ваша задача — помочь спроектировать такой Забор.
В первой строке записаны два целых числа N и K (3 ≤ K ≤ N ≤ 230). В следующих N строках содержатся пары целых чисел — координаты башен в порядке обхода границы против часовой стрелки. Гарантируется, что никакие три последовательные башни не лежат на одной прямой. Все координаты не превосходят 1000 по абсолютной величине.
В первую строку запишите максимальную площадь, которую можно защитить Забором, с точностью до пяти знаков после десятичной точки. Во второй строке должно быть Q — количество выбранных башен.
Будем считать, что башни занумерованы числами от 1 до N в порядке перечисления их во входном файле. Во третью строку через пробел выведите номера Q башен, которые будут вершинами Забора, в порядке его обхода против часовой стрелки.
Частичные ограничения
Первая группа состоит из тестов, в которых N ≤ 20 и граница Флатландии представляет собой выпуклый многоугольник.
Вторая группа состоит из тестов, в которых N ≤ 20, но граница может быть уже любой.
3 3 0 0 1 0 0 1
0.50000 3 1 2 3
6 5 0 0 7 0 4 3 4 4 3 4 0 7
24.50000 5 1 2 3 5 6
4 3 0 0 1 3 0 2 -2 -2
2.00000 3 1 3 4