Вычислительная геометрия

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

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

Формат входных данных
Вам даны 8 целых чисел - \(x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4\), где \((x_1, y_1)\) - координаты левого нижнего угла рисунка Пети, \((x_2, y_2)\) - координаты правого верхнего угла рисунка. Аналогично, \((x_3, y_3)\) - координаты левого нижнего угла вырезанного Васей прямоугольника, \((x_4, y_4)\) - координаты правого верхнего угла вырезанного прямоугольника. Гарантируется, что данные прямоугольники невырождены (\(x_1 < x_2\), \(y_1 < y_2\) и аналогичные неравенства для второго набора координат). Листок был не очень большим, поэтому каждое число по модулю не превосходит \(10^4\).

Формат выходных данных
Выведите YES, если Вася испортил рисунок, и NO в противном случае.

Примечание

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

Формат входных данных
    В первой строке содержится N (3 ≤N ≤1000) – число вершин многоугольника. В последующих N строках идут координаты (X_i, Y_i) вершин многоугольника в порядке обхода по часовой стрелке. X_i и Y_i - целые числа, по модулю не превосходящие 1000000.

Формат выходных данных
Вывести одно число – искомое число точек.

Примеры

№	Входные данные	Выходные данные
1	4 -1 -1 -1 1 1 1 1 -1	1
2	3 0 0 0 2 2 0	0

Саша и Маша живут в разных домах одного района. Их дома находятся возле пруда в форме квадрата. Однажды глава района предложил жителям нарисовать тропинки, которые они хотели бы видеть в своём районе, чтобы в дальнейшем проложить их. Потому ребята решили рассчитать самый короткий маршрут, который может быть, чтобы пройти от одного дома к другому. На изображении ниже представлен вариант расположения пруда и двух домов ребят (зелёная точка и оранжевая). Требуется рассчитать, какое самое кратчайшее расстояние требуется им преодолеть, чтобы оказаться друг у друга в гостях.


Примечание:

• дома могут находиться как по разные стороны пруда, так и поодну;
• требуется рассчитать ответ с точностью до десятых (если ответполучился целый, то выводить всегда после запятой один знак);
• передвигаться можно только по прямым, но не дугам;
• стороны пруда всегда параллельны осям OX и OY;
• точки, обозначающие дома могут лежать на границе пруда, и передвигать по границе пруда разрешено. 

Формат входных данных
На первой строке подаются параметры пруда через пробел a, x1, y1 (1 <= a <= 1000; -1000 <= x1,y1 <= 1000), где x1,y1 – координаты левого верхнего угла пруда.
На второй строке подаются координаты дома Маши в виде точки xm, ym (-1000 <= xm, ym <= 1000).
На третьей строке подаются координаты дома Саши в виде точки xs, ys (-1000 <= xs, ys <= 1000).
Все числа - целые.
Формат выходных данных
Выведите на одной строке самое кратчайшее расстояние, которое можно пройти от дома Маши к дому Саши. Ответ представляет собой всегда вещественное число с одним знаком после запятой. Если ответ получился больше, то округлить до одного знака после запятой (было 4.5764, стало 4.6).

 

Тимофею на день рождения родители подарили металлоискатель. Естественно, наутро мальчик отправился на поиски клада. Он предположил, что когда-то давно кто-то мог обронить золотую монету на древней прямой дороге и для облегчения поиска придумал систему координат. Ось абсцисс OX направлена вдоль дороги, а ось ординат OY направлена вверх.
Устройство работает следующим образом: на его индикаторе выставляется натуральное число r и если ровно на этом расстоянии имеется золотой предмет, то загорается зелёная лампочка.
Сначала юный кладоискатель выставил число r1 в точке x = 0, затем отошёл в точку с абсциссой x = a и выставил число r2, как показано на рисунке. Новичкам везёт, оба раза загорелась зелёная лампочка. Определите координаты потерянной когда-то давно золотой монетки.

Формат входных данных
Программа получает на вход три целых числа a, r1 и r2, записанных в отдельных строках (1 ≤ a, r₁, r₂ ≤ 10⁹ ).
Формат выходных данных
Выведите в двух строках два числа – координаты сокровища (сначала — абсциссу, потом — ординату). Значение ординаты должно быть не положительным (монетка не может висеть в воздухе). Гарантируется, что входные данные таковы, что ответ существует и обе координаты монеты будут целыми числами.

Замечание
Рисунок соответствует примеру из условия.

«Кто ходит в гости по утрам, тот поступает мудро…»

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

К сожалению, однажды Винни-Пуху пришла в голову идея вырыть ловушку для Слонопотама. Самое обидное, что они с Пятачком ее даже вырыли. Поэтому теперь каждое утро, идя в гости к Кролику, они боятся в нее провалиться.

Напишите программу, которая посчитает длину самого короткого безопасного пути от домика Винни-Пуха до домика Кролика.

Ловушка для Слонопотама представляет собой яму абсолютно круглой формы. Путь является безопасным, если он не проходит по ловушке (но может проходить по ее границе).

Формат входных данных

Во входном файле записаны сначала координаты домика Винни-Пуха X_В Y_В, затем — координаты домика Кролика X_К Y_К, а затем — координаты центра и радиус ловушки X_Л Y_Л R_Л. Все координаты — целые числа из диапазона от –32000 до 32000. Радиус ловушки — натуральное число, не превышающее 32000.

Домики Винни-Пуха и Кролика не могут находиться внутри ловушки, но могут находиться на ее границе.

Формат выходных данных

Выведите в выходной файл одно число — длину самого короткого безопасного пути от домика Винни-Пуха до домика Кролика с тремя знаками после точки.

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

Поскольку Винни Пух очень любит покушать, то в данной задаче (да и не только в задаче) примем его за сферу радиуса  P. Центр медведя находится на высоте Hp над уровнем земли. Строго над медведем , находится еще одна сфера, радиуса S – воздушный шарик; центр шарика находится на высоте Hs над уровнем земли. Центры обеих сфер находятся на одной вертикальной прямой.  По понятным причинам гарантируется, что сферы не пересекаются J, однако могут касаться.

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

Формат входных данных

C клавиатуры вводятся положительные целые числа P, Hp, S и Hs, не превосходящие 10000.

Формат входных данных

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

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

Создайте структуру Point и сохраните исходные данные в массиве структур Point.

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

Программа получает на вход набор точек на плоскости. Сначала задано количество точек n (2<n<101), затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Все исходные координаты – целые числа, не превосходящие 10³.

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

Необходимо вывести найденную площадь с точностью в 15 значащих цифр.

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

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

Программа получает на вход набор точек на плоскости. Сначала задано количество точек n (2<n<101), затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Все исходные координаты – целые числа, не превосходящие 10³.

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

Необходимо вывести  найденный периметр с точностью в 15 значащих цифр.

У игрока в космической стрелялке есть очень мощная лазерная пушка. Но она неподвижна и может стрелять только в одном направлении. Игрок может расставить на игровом поле двусторонние зеркала, меняющие ход луча, чтобы поражать врагов. Введём декартову систему координат с центром, где расположена пушка, то есть пушка имеет координаты (0; 0). Пушка стреляет в направлении точки (1; 1). Игрок может поставить зеркала в точках с целочисленными координатами. Зеркала могут быть горизонтальными или вертикальными, попадание луча в зеркало меняет траекторию луча по законам отражения света. Некоторые возможные варианты отражения луча от зеркала изображены на рисунке.

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

Входные данные
Программа получает на вход два целых числа X и Y , не превосходящих по модулю 10000, записанные в разных строках — координаты цели. Точка (X; Y) не совпадает с началом координат.

Выходные данные
Программа должна вывести в первой строке число N — необходимое количество зеркал. Следующие N строк должны содержать информацию о каждом зеркале. В i-й строке должны быть записаны через пробелы два целых числа xi и yi и один символ ti , обозначающие координаты (xi ; yi) точки, в которых установлено i-е зеркало, и тип этого зеркала ti . Если ti является символом «V», то i-е зеркало размещено вертикально, если же ti является символом «H», то зеркало размещено горизонтально. Например, строка «-2 5 H» обозначает горизонтальное зеркало в точке (−2; 5). Зеркала можно выводить в любом порядке. Зеркало нельзя размещать в точке (0; 0), также нельзя размещать два зеркала в одной точке. Значения xi и yi не должны по модулю превосходить 100 000. Также, разумеется, нельзя допустить, чтобы отражённый луч попал в пушку. Если вариантов ответа несколько, выведите любой из них. Если поразить цель в соответствии с условиями задачи невозможно, программа должна вывести одно число «-1». Если для поражения цели зеркала не нужны, программа должна вывести одно число «0»
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 1	1 3 3 H

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

Создайте структуру Point и сохраните исходные данные в массиве структур Point.

Входные данные
Программа получает на вход набор точек на плоскости. Сначала задано количество точек n, затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Величина n не превосходит 100, все исходные координаты – целые числа, не превосходящие 10³.

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

 Примеры

№	Входные данные	Выходные данные
1	2 1 2 2 3	1 2 2 3

Входные данные
В первой строке вводятся три целых числа – N (3≤N≤100000) и координаты точки. Далее в N строках задается по паре целых чисел – координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.

Выходные данные
Выведите  одну строку: “YES”, если заданная точка содержится в приведённом многоугольнике или на его границе, и “NO” в противном случае.
 

Примеры

№	Входные данные	Выходные данные
1	3 2 3 1 1  10 2 2 8	YES

Входные данные
Семь чисел – координаты центра и радиус окружности (возможно, вырожденной) и вещественные координаты двух точек на ней, с точностью до пятого знака после запятой.

Выходные данные
Одно число – длина меньшей дуги окружности, заключённой между указанными точками.
 

Примеры

№	Входные данные	Выходные данные
1	0 0 1 0 1 1 0	1.57080

Входные данные
Шесть чисел – координаты центра и радиусы двух окружностей.

Выходные данные
В случае, если количество общих точек окружностей конечно, в первой строке вывести одно число K, равное этому количеству, далее в K строках координаты самих точек. Если указанных точек бесконечно много, вывести единственное число “3”.
 

Примеры

№	Входные данные	Выходные данные
1	3 4 5 11 4 2	0
2	3 4 5 9 4 2	2 7.75000 5.56125 7.75000 2.43875

Входные данные
Шесть чисел – координаты центра и радиус окружности и коэффициенты A, B и C нормального уравнения прямой.

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

Примеры

№	Входные данные	Выходные данные
1	2 3 1 1 -1 0	2 3.00000 3.00000 2.00000 2.00000

Входные данные
Пять чисел – координаты центра и радиус окружности, координаты точки.

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

Примеры

№	Входные данные	Выходные данные
1	2 2 2 2 5	2 0.50929 3.33333 3.49071 3.33333

Входные данные
Шесть чисел – координаты точек X, Y и Z.

Выходные данные
Три числа – коэффициенты уравнения биссектрисы угла YXZ.

Примеры

№	Входные данные	Выходные данные
1	0 0 1 0 0 1	1.000000 -1.000000 0.000000
2	0 0 1 3 1 -3	0.000000 -0.632456 0.000000

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

Вася, если честно, не очень понял тему про параллелограммы, и ему требуется программа, умеющая правильно отвечать на Петины вопросы.

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

Входные данные
В первой строке входного файла записано целое число N (1 ≤ N ≤ 10) - количество заданных Петей вопросов. Каждая из N последующих строк содержит описание четырех точек - четыре пары целых чисел X и Y (−100 ≤ X ≤ 100, −100 ≤ Y ≤ 100), обозначающих координаты точки.

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

Примеры

№	Входные данные	Выходные данные
1	3 1 1 4 2 3 0 2 3 1 1 5 2 2 3 3 0 0 0 5 1 6 3 1 2	1 3 2 4 0 1 2 3 4

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

Изначально, до появления Байтландии, на её территории были расположены n различных стран. Каждое государство владело своей территорией, которую можно было представить на карте как прямоугольник, стороны которого параллельны осям координат, а вершины расположены в целочисленных точках. Никакие две страны не пересекались, однако они могли касаться сторонами. Иногда в результате агрессивных переговоров и мирных военных походов две страны объединялись в одну. Слияние происходило только в том случае, если после объединения их владений снова получалась прямоугольная территория. В конце концов осталось только одно государство — Байтландия.

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

Входные данные
Первая строка содержит одно целое число n (1 ≤ n ≤ 100000) — количество замков и стран.

Каждая из следующих n строк содержат четыре целых числа a_i, b_i, c_i, d_i (0 ≤ a_i  < c_i ≤ 10⁹, 0 ≤ b_i < d_i ≤ 10⁹) — координаты вершин i-го замка, где (a_i, b_i) — координаты левой нижней точки, а (c_i, d_i) — правой верхней.

Гарантируется, что никакие два замка не пересекаются, однако они могут касаться сторонами.

Выходные данные
Если существуют расположения изначальных стран, для которых верна данная история, то выведите « YES », иначе выведите « NO ».

Примечание
На картинках ниже изображено расположение замков в первом и втором примере.

Примеры

№	Входные данные	Выходные данные
1	4 0 0 1 2 0 2 1 3 1 0 2 1 1 1 2 3	YES
2	4 0 0 2 1 1 2 3 3 2 0 3 2 0 1 1 3	NO

В 2037-м году для создания научно исследовательской базы на Марс высадился отряд роботов, один из которых отправился собирать информацию о районе дислокации. В данный момент роботу из-за отказа некоторых узлов срочно необходимо вернуться в место закладки будущей базы.
Поверхность Марса в районе высадки десанта можно условно представить в виде плоскости с введенной на ней системой координат, такой, что база находится в точке (0, 0). Робот же остановился в точке (x₀, y₀). Он может перемещаться в четырёх направлениях:
• «R» — вправо, при этом координата x робота увеличивается на 1;
• «L» — влево, при этом координата x робота уменьшается на 1;
• «U» — вверх, при этом координата y робота увеличивается на 1;
• «D» — вниз, при этом координата y робота уменьшается на 1.
Из-за неисправности робот не может совершить два перемещения подряд в одном направлении.
Помогите роботу вернуться на базу. Робот должен сделать не более 10000 передвижений, иначе он разрядится и не доедет до базы!

Входные данные
В единственной строке входных данных находятся два целых числа x0 и y0 — изначальные координаты робота (−1000 ≤ x0, y0 ≤ 1000).

Выходные данные
В первой строке выведите целое число, не большее 10000 — количество операций, которые должен сделать робот. Во второй строке выведите сами операции. Каждая операция задаётся одной буквой:
вправо — «R» влево — «L», вверх — «U», вниз — «D». Символы необходимо выводить без пробелов между ними.
 

Примеры

№	Входные данные	Выходные данные
1	2 1	5 DLULD

Замечание
Вы не обязаны выводить кратчайший маршрут. Например, в приведенном примере кратчайший
маршрут состоит из 3 передвижений: влево, вниз, влево.
Иллюстрация к тесту из примера:

Беда! К городу N приближается метеорит. Людей уже успели эвакуировать, но домам урона не избежать. Ученые уже выяснили, куда упадет метеорит. Вас, как сотрудника страховой компании, попросили выяснить количество домов, которые пострадают при падении метеорита.

Введём на плоскости прямоугольную систему координат. Город представляет собой прямоугольник n × m . Его левый нижний угол расположен в точке с координатами (0, 0) , а правый верхний угол в точке с координатами ( n - 1, m - 1) . В каждой точке с целыми координатами внутри или на границе этого прямоугольника находится дом. Дома в городе N маленькие, поэтому их можно считать точками.

Известно, что метеорит упал в точку ( x , y ) , а радиус его поражения равен r . Таким образом, все дома города на расстоянии не более r от точки падения метеорита получат повреждения. Найдите количество домов, которые получат повреждения.

Входные данные
Первая строка содержит два целых числа n , m ( 1 ≤ n , m ≤ 500 ) — размеры города N.

Вторая строка содержит три целых числа x , y , r ( - 500 ≤ x , y ≤ 500 ; 0 ≤ r ≤ 500 ) — координаты точки падения метеорита и радиус поражения, соответственно.

Выходные данные
Выведите одно число — количество повреждённых домов.

Примечание
Иллюстрация к тесту из примера: чёрными точками обозначены повреждённые дома, белыми — уцелевшие.

Примеры

№	Входные данные	Выходные данные
1	2 3 1 2 1	3