Алгоритмы

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

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

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

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3. Все числа целые, по модулю не превосходят 1000.

Выходные данные
Выведите три числа X, Y, R, задающие координаты центра и радиус окружности, описанной вокруг треугольника, образованного данными точками. Числа в ответе должны быть выданы с точностью не менее 5 знаков после десятичной точки.

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3. Все числа целые, по модулю не превосходят 1000.

Выходные данные
Выведите три числа: X, Y, R, задающие координаты центра и радиус окружности, вписанной в треугольник, образованный данными точками. Числа в ответе должны быть выданы с точностью не менее 5 знаков после десятичной точки.

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3. Все числа целые, по модулю не превосходят 1000.

Выходные данные
Выведите два числа X, Y, задающие координаты точки пересечения биссектрис в треугольнике, образованном исходными точками. Числа в ответе должны быть выданы с точностью не менее 5 знаков после десятичной точки.

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3. Все числа целые, по модулю не превосходят 1000.

Выходные данные
Выведите два числа X, Y, задающие координаты точки пересечения медиан в треугольнике, образованном  исходными точками. Числа в ответе должны быть выданы с точностью не менее 5 знаков после десятичной точки.

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3. Все числа целые, по модулю не превосходят 1000.

Выходные данные
Выведите два числа: X и Y, задающие координаты точки пересечения высот в треугольнике, образованном исходными точками. Числа в ответе должны быть выданы с точностью не менее 5 знаков после десятичной точки.

Входные данные
Пять чисел - коэффициенты A, B и C уравнения прямой и координаты некоторой точки X, Y (точка может быть как на прямой, так и вне ее). Все числа целые, по модулю не превосходят 1000.

Выходные данные
Выведите три числа - коэффициенты A, B и C уравнения прямой, перпендикулярной заданной и проходящей через заданную точку. Числа в ответе должны быть выданы с точностью не менее 5 знаков после десятичной точки.

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

Входные данные
Вводятся сначала координаты двух различных точек, через которые проходит первая прямая, а затем - координаты еще двух различных (но, быть может, совпадающих с первыми двумя) точек, через которые проходит вторая прямая. Координаты каждой точки - целые числа, по модулю не превышающие 1000.

Выходные данные
Если прямые не пересекаются, выведите одно число 0. Если прямые совпадают, выведите 2. Если прямые пересекаются ровно в одной точке, то выведите сначала число 1, а затем два вещественных числа - координаты точки пересечения.

Выполняя очередное задание Министерства образования и сельского хозяйства, программисты Флатландского государственного университета информационных технологий, удобрений и ядохимикатов создали специального робота по прокладке оросительных каналов.

Программа для робота представляет собой последовательность команд. Команды робота приведены в следующей таблице:

Команда	Обозначение	Действия робота
Перемещение	(X)	Переместиться вперед на X километров, прокладывая за собой оросительный канал
Поворот налево	L	Повернуть налево на 90o
Поворот направо	R	Повернуть направо на 90o

Любая программа начинается и заканчивается командами перемещения и не содержит двух команд перемещения или двух команд поворота подряд.

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

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

Входные данные
Входные данные содержат команды поворота исходной программы в том порядке, в котором они в ней следовали. Каждая команда представляет собой символ «L» либо «R», команды друг от друга не отделяются. Количество команд не превышает 30 000.

Выходные данные
Выведите  любую корректную программу, последовательность команд поворота в которой совпадает с последовательностью, заданной во входных данных. Параметр X каждой команды перемещения должен быть положительным целым числом и не должен превышать 10⁹. Все команды выведите в одной строке и друг от друга не отделяйте.

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

На определенном этапе игры Сережа столкнулся с неожиданной проблемой. Для продолжения приключений герою надо перебраться через пропасть. Для этого можно использовать последовательно расположенные лифты, которые имеют вид горизонтальных платформ. Каждый лифт вертикально перемещается туда-сюда между некоторыми уровнями. Герой может переходить между соседними платформами, однако это можно сделать только в тот момент, когда они находятся на одном уровне. Аналогично с края пропасти на лифт и обратно можно перейти лишь в тот момент, когда лифт окажется на уровне края.

Каждый лифт имеет ширину равную четырем метрам. В начале герой находится на расстоянии два метра от края пропасти. Он должен закончить свое путешествие в двух метрах от противоположного края пропасти. Герой перемещается со скоростью два метра в секунду. Таким образом, если герой находится в начальном положении или в центре лифта и хочет перейти на соседний лифт (или сойти с последнего лифта на противоположный край пропасти), он должен начать движение ровно за одну секунду до того момента, когда они окажутся на одном уровне. Через две секунды герой оказывается в центре соседнего лифта (или в конечном положении).

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

Формат входных данных
Первая строка содержит целое число \(n\) — количество лифтов (\(1 \le n \le 100\)). Следующие \(n\) строк содержат описания лифтов.

Каждое описание состоит из четырех целых чисел: \(l\), \(u\), \(s\) — самое нижнее, самое верхнее и начальное положение лифта относительно края пропасти в метрах (\(-100 \le l \le s \le u \le 100\), \(l < u\)), и \(d\) — направление движения лифта в начальный момент (\(d = 1\) означает, что лифт двигается вверх, \(d = -1\) — вниз).

Формат выходных данных
Выведите минимальное время в секундах, необходимое чтобы перебраться на противоположный край пропасти. Если перебраться на противоположный край пропасти невозможно, выведите в выходной файл \(-1\).

В одном феодальном государстве средневековой Европы было \(n\) городов и \(m\) дорог, каждая из которых соединяла некоторые два города. Каждая дорога принадлежала правителю одного из городов (не обязательно одного из тех, которые она соединяла). Однажды правитель города S решил объявить войну правителю города T. Перед ним сразу же встала нелегкая задача: как довести армию до города T.

Правитель каждого города требует плату за проход войск через его город. Кроме того, правитель города S может перемещать войска только по дорогам, которые принадлежат ему. При этом он может купить любую дорогу у ее владельца за определенную плату (даже если владелец — правитель города T). К сожалению, все деньги из казны города S были потрачены на предыдущий неудачный военный поход, поэтому сначала правителю придется продать некоторые свои дороги (разумеется, после этого он не сможет провести по ним войска).

Помогите правителю выяснить, какие дороги следует продать, а какие купить, чтобы довести войска от города S до города T и оплатить проход через все промежуточные города. Все операции продажи и покупки дорог надо осуществить до начала похода, пока правители других городов не догадались о воинственных намерениях правителя города S.

Формат входных данных
Первая строка содержит целые числа \(n\) и \(m\) — количество городов и дорог соответственно (\(2 \le n \le 2\,000\), \(1 \le m \le 50\,000\)). Города нумеруются от 1 до \(n\), города S и T имеют номера 1 и \(n\) соответственно.

Следующие \(n\) строк содержат под одному целому числу \(r_i\) — плату за проезд через город \(i\) (\(0 \le r_i \le 10\,000\), \(r_1 = r_n = 0\)).

Следующие \(m\) строк содержат описания дорог. Дорога описывается четырьмя целыми числами: \(a_i\), \(b_i\), \(p_i\) и \(c_i\). Здесь \(a_i\) и \(b_i\) — номера городов, которые соединяет дорога, \(p_i\) — номер города, правителю которого она принадлежит, \(c_i\) — ее стоимость (\(a_i \ne b_i\), \(1 \le c_i \le 10\,000\)). По дороге можно перемещаться в обоих направлениях. Любые два города соединены не более чем одной дорогой.

Формат выходных данных
На первой строке выведите список дорог, которые нужно продать в следующем формате: сначала число дорог, а затем их номера. Дороги нумеруются с единицы в том порядке, в котором они заданы во входных данных. На второй строке выведите список дорог, которые нужно купить, в том же формате. На третьей строке выведите маршрут похода — номера городов в порядке следования войска. Если решений несколько, выведите любое.

Если решения нет, выведите в выходной файл число \(-1\).

Ребята во дворе решили поиграть в прятки. Чтобы выбрать ведущего, который будет искать, они решили воспользоваться считалкой. Считалка состоит из \(k\) слов, и используется следующим образом.

Все \(n\) ребят становятся в круг и один из них, начиная с себя, по очереди указывает на ребят в порядке, в котором они стоят по кругу, называя слова считалки. Тот, на кого указывает считающий, называя последнее слово считалки, выбывает из круга. После этого считалка повторяется сначала, а счет начинается со следующего за выбывшим. Так продолжается до тех пор, пока в круге не останется один человек. Он то и будет ведущим.

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

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

Помогите им ответить на этот вопрос.

Формат входных данных
Строка содержит два целых числа — \(n\) и \(k\) (\(1 \le n \le 1000\), \(1 \le k \le 10^9\)).

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

При разработке программ для просмотра веб-страниц одной из наиболее сложных задач является корректное отображение таблиц. Компания <<Kozilla>>, в которой вы работаете, планирует разработать новую версию браузера <<Waterrat>> для работы в терминальном режиме, и просит вас написать фрагмент ядра отображения веб-страниц, ответственный за формирование структуры таблиц.

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

Таблица состоит из строк, каждая строка состоит из одной или нескольких ячеек, \(j\)-я ячейка \(i\)-й строки имеет ширину \(a_{i,j}\).

По заданным параметрам таблицы постройте символическое изображение ее структуры.

Формат входных данных
Первая строка содержит \(n\) — количество строк в таблице (\(1 \le n \le 100\)). Следующие \(n\) строк входного файла содержат описание строк таблицы.

Описание каждой строки включает число \(m_i\) — количество ячеек этой строки, и \(m_i\) целых чисел \(a_{i,1}, a_{i,2}, \dots, a_{i,m_i}\) — ширину каждой из ячеек строки (\(1 \le m_i \le 10\), \(1 \le a_{i,j} \le 20\)).

Формат выходных данных
Выведите символическое изображение структуры таблицы.

Изображение \(i\)-й строки таблицы должно начинаться изображением горизонтальной линии, составленным из символов <<+>> (плюс) и <<->> (минус). Затем должна следовать строка, содержащая пробелы и символы <<|>> (вертикальная черта). Первым символом строки должна быть вертикальная черта, затем \(a_{i,1}\) пробелов, затем вертикальная черта, затем \(a_{i,2}\) пробелов, и так далее, всего \(m_i\) блоков пробелов. После последнего блока должна следовать вертикальная черта. После последней строки таблицы также должно следовать изображение горизонтальной линии.

В изображении горизонтальной линии используйте символ <<+>>, если сверху или снизу от этой позиции находится вертикальная черта, и <<->> в противном случае. Горизонтальная линия должна иметь минимальную возможную длину, чтобы над каждым символом вертикальной черты следующей строки и под каждым символом вертикальной черты предыдущей строки были символы <<+>>.

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

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

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

Формат входных данных
На первой строке записано целое число \(n\) — количество этапов эксперимента (\(1 \le n \le 100\)).

Следующие \(n\) строк содержат описание этапов. Пронумеруем этапы от 1 до \(n\) в некотором произвольном порядке. Тогда \(i\)-я из этих строк описывает \(i\)-й этап. Каждый этап описывается последовательностью целых чисел. Первое число равно нулю, если на этом этапе Игорь управляет генератором, и единице, если он управляет манипулятором. Затем записано целое число \(r_i\) — количество этапов, которые должны быть выполнены перед выполнением данного. За ним следуют номера этих этапов — \(r_i\) различных целых чисел в диапазоне от 1 до \(i - 1\).

Формат выходных данных
На первой строке выведите минимальное количество перемещений, которые придется совершить Игорю. На второй строке выведите перестановку чисел от 1 до \(n\) — последовательность, в которой следует выполнять этапы. Если решений несколько, выведите любое.

Сегодня на страницах газеты <<Математический досуг>> была опубликована необычная математическая головоломка. Одна из страниц газеты полностью занята прямоугольной таблицей, состоящей из \(m\) строк и \(n\) столбцов. В каждой ячейке таблицы записано некоторое целое число.

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

Безуспешно потратив несколько часов на решение головоломки, Саша решил написать программу, которая сделала бы это за него. Но и тут его постигла неудача. Теперь ему ничего не остается, как обратиться за помощью к вам.

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

Формат входных данных
На первой строке записаны два целых числа \(m\) и \(n\) (\(2 \le m, n \le 300\)). Далее следует описание таблицы — \(m\) строк, каждая из которых содержит по \(n\) целых чисел \(a_{i,j}\) (\(-10^4 \le a_{i,j} \le 10^4\)).

Формат выходных данных
На первой строке выведите целое число \(s\) — максимальную сумму чисел на границе искомого прямоугольника. На второй строке выведите четыре натуральных числа: \(x_1, y_1, x_2, y_2\) — координаты левой верхней и правой нижней ячейки выбранного прямоугольника, соответственно (здесь \(x\) — номер строки, а \(y\) — номер столбца, строки нумеруются сверху вниз, начиная с единицы, столбцы нумеруются слева направо, начиная с единицы). Если оптимальных решений несколько, выведите любое.

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

Однако все оказалось совсем не так просто. Художник изготовил рамку, поместил в нее картину и понял, что что-то не так. Рамка получилась слишком широкой, и картина выглядела совсем не так ярко, как он ожидал.

Немного поразмыслив, художник понял, что то, насколько рамка <<подходит>> для картины, определяется площадью рамки. Кроме этого он понял, что рамки надо не изготавливать самостоятельно, а покупать в специальном магазине. Заглянув в прайс-лист магазина, он увидел, что для каждой рамки в нем указаны длины внешних сторон и ширина.

Поясним подробнее то, как выглядит треугольная рамка. Ее изготовление происходит следующим образом: берется доска из красного дерева, имеющая форму треугольника со сторонами \(a\), \(b\) и \(c\). После этого стороны этого треугольника мысленно сдвигаются внутрь него на расстояние \(d\) (измеряемое по перпендикуляру к соответствующей стороне). На точках пересечения <<сдвинутых>> сторон строится маленький треугольник, который затем вырезается из исходного. Пример рамки со сторонами \(a=6\), \(b=8\), \(c=10\) и шириной \(d=1\) показан на рисунке.

Помогите художнику по имеющимся в прайс-листе данным вычислить площадь рамки.

Формат входных данных
Входные данные содержит четыре целых числа \(a\), \(b\), \(c\), \(d\) (\(1 \le a, b, c, d \le 1000\)) — длины внешних сторон рамки и ее ширину, соответственно. Гарантируется, что треугольник со сторонами \(a\), \(b\) и \(c\) существует, и что в треугольнике есть точка, расстояние от которой до ближайшей стороны строго больше \(d\).

Формат выходных данных
Выведите площадь рамки с точностью не меньше \(10^{-5}\).

В комнате у Аркадия Семеновича Тапкина стоят электронные часы. Цифры на этих часах показываются в специальной псевдографике. А именно каждое поле, на котором изображается цифра, состоит из \(w\) ячеек в ширину и \(h\) ячеек в высоту (при этом ячейки на поле имеют форму квадратов).

Но недавно у Аркадия Семеновича появилась проблема. Последнее время он стал плохо видеть. В связи с этим он хочет увеличить изображение этих цифр. Он уже приладил старый \(19''\) монитор к часам, и теперь дело осталось за малым. Осталось написать программу, которая будет рисовать цифры на дисплее. Аркадий Семенович хочет увеличить изображение в \(k\) раз и сделать толщину линий равной \(d\). Помогите ему в этом.

Опишем более формально понятие <<увеличить в \(k\) раз>>. Занумеруем ячейки поля \(w \times h\) сверху вниз и слева направо. Таким образом, верхняя левая ячейка имеет координаты \((0, 0)\), правая нижняя — \((w - 1, h - 1)\), правая верхняя — \((w - 1, 0)\), левая нижняя — \((0, h - 1)\). Кроме этого, введем декартову прямоугольную систему координат так, что начало координат находится в центре верхней левой ячейки, ось \(Ox\) направлена вправо, ось \(Oy\) — вниз, длину единичного отрезка примем равной длине стороны ячейки. Таким образом, координаты центра ячейки совпадают с ее координатами во введенной нумерации.

Каждая десятичная цифра задается набором составляющих ее изображение отрезков. Для простоты каждый из отрезков либо параллелен одной из координатных осей, либо идет под углом в 45 градусов к ней.

Увеличенная в \(k\) раз цифра рисуется на поле размером \((w - 1) \cdot (k - 1) + w\) ячеек по горизонтали на \((h - 1) \cdot (k - 1) + h\) ячеек по вертикали.

При увеличении некоторой цифры в \(k\) раз производятся следующие операции. Координаты точек, являющихся концами отрезков, составляющих цифру, умножаются на \(k\). После этого закрашиваются те ячейки, через центры которых проходят эти отрезки. Эти ячейки будем называть основными.

После этого, для того, чтобы получить толщину линий равную \(d\), дополнительно закрашиваются те ячейки, центры которых располагаются на расстоянии, не превышающем \((d - 1)\) от центров основных ячеек. Расстоянием между точками \(A(x_A, y_A)\) и \(B(x_B, y_B)\) будем называть число \(\rho(A, B) = |x_A - x_B| + |y_A - y_B|\).

По описанию цифры и параметрам \(k\) и \(d\) выведите изображение цифры, увеличенное в \(k\) раз, с толщиной линий \(d\).

Формат входных данных
Первая строка содержит целые числа \(k\) и \(d\) (\(1 \le k \le 100\), \(1 \le d \le 500\)). Вторая строка содержит целые числа \(w\) и \(h\) (\(1 \le w, h \le 10\)).

Третья строка содержит целое число \(n\) (\(1 \le n \le 100\)) — количество отрезков в описании цифры. Далее следуют \(n\) строк, каждая из которых описывает один отрезок. Описание отрезка состоит из четырех целых чисел: \(x_1\), \(y_1\), \(x_2\), \(y_2\) (\(0 \le x_1, x_2 < w\), \(0 \le y_1, y_2 < h\)) — координат концов отрезка.

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

Формат выходных данных
Выходные данные должны содержать ровно \((h - 1) \cdot (k - 1) + h\) строк по \((w - 1) \cdot (k - 1) + w\) символов в каждой, \(j\)-ый символ \(i\)-ой строки должен быть равен символу <<*>> (звездочка), если ячейка с центром в точке \((j,i)\) закрашена, и символу <<.>> (точка) — иначе.

Два радара, расположенные в точках с координатами (0, 0) и (100, 0), обнаружили неопознанный объект. По таинственной причине, связанной, возможно, с внеземной природой объекта, радары оказались способны определить только направление на объект (пеленг), но не расстояние до объекта. Пеленг измеряется в градусах, против часовой стрелки, начиная от направления "на восток" (т. е. пеленг второго радара относительно первого равен 0°, пеленг первого радара относительно второго - 180°).

Требуется найти координаты НЛО или определить, что это невозможно.

Входные данные
Во входном файле содержатся вещественные числа a и b (0 <= a, b < 360), разделенные пробелами.

Выходные данные
В выходном файле должны содержаться два вещественных числа, x и y, представляющие координаты объекта с точностью до 4 знаков после запятой. Если определить координаты невозможно, следует вывести два числа 0 (нуль).

Даны восемь символов из диапазона от "A" до "Z". Некоторые из них могут совпадать. Требуется определить, можно ли расположить эти символы в вершинах куба таким образом, чтобы на соседних (т. е. соединенных ребром) вершинах оказались разные символы

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

Выходные данные
Выходной файл должен содержать целое число 1, если расположение возможно, и 0 (нуль) в противном случае.

Выпуклый N-угольник P преобразуется в N-угольник Q путём замены середин сторон исходного многоугольника P на вершины многоугольника Q. Требуется по выпуклому N-угольнику Q, заданному координатами вершин, восстановить координаты вершин исходного N-угольника P.

Входные данные
Входные данные содержит нечётное число вершин N (3 <= N <= 999), за которым следуют целочисленные координаты x_i y_i вершин многоугольника Q, перечисленные в порядке обхода по часовой стрелке. Значения координат находятся в диапазоне от -20000 до 20000. Все числа во входном файле целые и разделены произвольным количеством пробелов и/или символов перевода строки.

Выходные данные
В выходных данных должны содержаться координаты вершин N-угольника P, перечисленные в порядке обхода по часовой стрелке. При этом первая и вторая вершина должны образовывать сторону, на которой лежит первая вершина N-угольника Q.