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

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

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

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

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

Решите задачу быстрым методом

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

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

Заданы полярные координаты двух точек на плоскости. Требуется найти расстояние между этими точками.

Входные данные
Вводятся 4 числа, первые два задают радиус и полярный угол первой точки, последние два - второй. Обратите внимание: все углы задаются в градусах.

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

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

Входные данные
Сначала вводится число 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, а затем два вещественных числа - координаты точки пересечения.

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

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

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

Входные данные
Будем считать, что в городе введена прямоугольная декартова система координат.

Первые две строки входных данных описывают велосипедные дорожки. Каждая из них содержит по три целых числа – координаты центра окружности, которую представляет собой соответствующая дорожка, и ее радиус. Координаты и радиус не превышают 200 по абсолютной величине, радиус – положительное число. Гарантируется, что дорожки не совпадают.

Следующие две строки содержат по два вещественных числа – координаты точки, где Петя заезжает на дорожку, и точки, в которой Петя съезжает с дорожки. Гарантируется, что каждая из точек с высокой точностью лежит на одной из дорожек (расстояние от точки до центра одной из окружностей отличается от ее радиуса не более, чем на 10^-8). Точки могут лежать как на одной дорожке, так и на разных.

Выходные данные
Выведите  минимальное расстояние, которое следует проехать Пете по велосипедным дорожкам, чтобы попасть из дома в школу. Ответ должен отличаться от правильного не более, чем на 10^-4.

Если доехать из дома до школы по велосипедным дорожкам невозможно, выведите  число -1.

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

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

Степень точки \(A\) относительно многоугольника вычисляется по следующему правилу. Рассмотрим все лучи с вершиной в точке \(A\), имеющие общие точки с многоугольником. Для каждого такого луча найдем минимальное и максимальное расстояние вдоль него от точки \(A\) до некоторой точки многоугольника: \(d_{min}\) и \(d_{max}\). Степенью точки относительно данного многоугольника назовем минимум величины \(d_{min}\times d_{max}\) по всем таким лучам.

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

Будем считать, что наблюдательный центр находится в точке \((0, 0)\). Входной файл содержит описание полигона.

Формат входных данных
Первая строка содержит число \(n\) — количество вершин полигона (\(3 \le n \le 100\)). Следующие \(n\) содержат по два вещественных числа — координаты вершин полигона в порядке обхода их против часовой стрелки. Координаты не превышают \(1000\) по абсолютной величине. Гарантируется, что наблюдательный центр находится вне полигона, полигон представляет собой выпуклый невырожденный многоугольник, никакие три его последовательных вершины не лежат на одной прямой. Никакая сторона многоугольника не лежит на луче с центром в начале координат.

Формат выходных данных
Выведите одно число — степень наблюдательного центра относительно полигона. Ответ должен отличаться от правильного не более чем на \(10^{-4}\).

На планете Плюк, поверхность которой мы будем считать абсолютно плоской, был разработан новый принцип перемещения единственного имеющегося там транспортного средства — пепелаца. А именно, на расстоянии одного километра друг от друга в точках \((0, 0)\) и \((1, 0)\) были построены две станции управления пепелацами \(A\) и \(B\). С помощью них можно мгновенно переместить любой пепелац, повернув его на 90 градусов по или против часовой стрелки относительно точки \(A\) или \(B\). Расстояние от пепелаца до соответствующей станции при этом не меняется. Следующее перемещение можно делать как относительно той же станции, так и относительно другой.

Например, если повернуть пепелац, находящийся в точке \((3, 1)\) на 90 градусов против часовой стрелки относительно станции \(A\), то он переместится в точку \((-1, 3)\), если его затем повернуть на 90 градусов по часовой стрелке относительно станции \(B\), то он переместится в точку \((4, 2)\), если затем повернуть его вокруг станции \(B\) по часовой стрелке еще раз, он переместиться в точку \((3, -3)\).

Один житель планеты недавно решил отправиться на своем пепелаце в гости к другу. Житель проживает около точки с координатами \((x_1, y_1)\), а его друг — около точки с координатами \((x_2, y_2)\). Помогите жителю с помощью станций управления пепелацем оказаться как можно ближе к месту, где проживает его друг, чтобы потом меньше было идти по пустыне.

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

Формат входных данных
Входные данные содержит четыре целых числа — \(x_1\), \(y_1\), \(x_2\) и \(y_2\), они не превышают \(10^4\) по абсолютной величине.

Формат выходных данных
Выведите последовательность перемещений с использованием станций управления, которая перемещает пепелац из точки \((x_1, y_1)\) как можно ближе к точке \((x_2, y_2)\).

Поворот по часовой стрелке относительно станции \(A\) обозначается как <<+A>>, поворот против часовой стрелки относительно станции \(A\) обозначается как <<-A>>, соответствующие повороты относительно станции \(B\) обозначаются как <<+B>> и <<-B>>. Выводите по одному перемещению на строке.

Выведенная последовательность не обязана быть минимальной по количеству перемещений, но должна содержать не более \(10^6\) действий.

Во Флатландии \(n\) городов, расположенных в различных точках плоскости. Известно, что никакие три города не лежат на одной прямой.

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

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

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

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

Ваша задача — таким образом сопоставить числам от 1 до \(n\) города, чтобы после реализации проекта шоссе не пересекались вне городов, которые они соединяют.

Формат входных данных
В первой строке содержится целое число \(n\) — количество городов во Флатландии (\(2 \le n \le 1500\)).

Далее следует \(n\) описаний городов. Описание каждого города состоит из двух строк. Первая строка содержит название города — строку, состоящую из символов с ASCII-кодами от 33 до 127. Названия различных городов не совпадают. Длина названия города не превышает 60 символов. Вторая строка описания города содержит два целых числа \(x\) и \(y\) — координаты города. Координаты не превышают \(10^4\) по абсолютной величине.

Далее следуют \(n - 1\) строк, которые описывают проект строительства сети шоссе в его текущем состоянии. Каждая строка содержит по два целых числа — номера городов, соединенных шоссе в проекте. Никакое шоссе в проекте не соединяет город сам с собой, никакие два города не соединены более чем одним шоссе.

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

Если решения не существует, выведите <<No solution>>.

Иллюстрация к примеру

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

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

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

Поясним подробнее то, как выглядит треугольная рамка. Ее изготовление происходит следующим образом: берется доска из красного дерева, имеющая форму треугольника со сторонами \(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}\).

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

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

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

Выходные данные
В выходном файле должны содержаться два вещественных числа, x и y, представляющие координаты объекта с точностью до 4 знаков после запятой. Если определить координаты невозможно, следует вывести два числа 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.

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

Входные данные
Во входном файле записано число деревьев N (2 <= N <= 14), а затем каждое дерево описано четырьмя числами x_i, y_i, v_i, l_i - координаты (целые от -10000 до 10000), цена и длина (от 0 до 10000).

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

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

Формат входных данных:
В первой строке дано число 0 <= N <= 1000. Далее записаны N строк. Каждая строка содержит два целых чисел через пробел 0 < x_i, y_i < 10⁶ - координаты вершины i-й ступени (ступени перечисляются в порядке сверху вниз, слева направо).

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

Примечание