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

В точке (0, 0) координатной плоскости расположена лампочка, которая представляет собой точечный источник света. Неподалеку от лампочки находится дом Пети, который представляет собой выпуклый многоугольник с N вершинами. Сам Петя находится в точке с координатами (x, y).

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

Петя может перемещаться по плоскости со скоростью v. Разумеется, Петя не может проходить сквозь дом (хотя он может двигаться по его границе).

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


Входные данные
В первой строке вводятся координаты Пети – два неотрицательных вещественных числа, не превышающих 1000, и его скорость v – вещественное число, 10^-2≤ v≤ 10⁴.

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

Гарантируется, что входные данные корректны, в частности, многоугольник выпуклый, и никакие три его последовательные вершины не лежат на одной прямой. Также гарантируется, что и Петя, и лампочка находятся снаружи от многоугольника, в частности, не находятся на его границе. Расстояние от точки, где находится Петя, до многоугольника и от начала координат до многоугольника не меньше 10^-2, расстояние от Пети до начала координат не меньше 10^-2.

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

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

Входные данные
В первой строке входных данных содержится число N – количество отмеченных Петей точек (1 ≤ N ≤ 100 000).

В каждой из следующих N строк записаны по два числа x_i, y_i – координаты точек, нарисованных Петей. Координаты по абсолютной величине не превосходят 10⁶. Некоторые точки могут совпадать.

Выходные данные
Требуется вывести одно число – периметр искомого многоугольника. Ответ нужно вывести с точностью не менее 0.001.

В ежегодном чемпионате Флатландии (которая, естественно, является плоским миром) по космическим гонкам "Формула-3" участвуют N космических скутеров, имеющие форму треугольников. До начала гонок скутеры занимают положение в стартовой зоне согласно результатам жеребьевки.


Скутеры стартуют строго по порядку. Каждый скутер,получив команду «старт», уезжает в положительном направлении оси Ox. Следующий скутер стартует лишь тогда, когда предыдущий покинет стартовую зону. Скутеры уезжают строго параллельно оси Ox, скутеры в стартовой зоне не поворачивают и не разворачиваются.

Естественно, что если в момент старта на пути скутера окажется другой скутер, то произойдет авария (даже если скутер заденет лишь угол другого скутера своим углом).

Для уменьшения опасности столкновения скутеров на старте строго соблюдается следующее правило: прямые, параллельные оси Ox и пересекающие какой-то скутер, должны в совокупности пересекать не более 100 других скутеров (прямая, проходящая через одну точку скутера также считается прямой, пересекающей скутер). Например, на приведенном рисунке прямые, параллельные Ox и пересекающие скутер 2, проходят через 2 других скутера (1 и 3), а прямые, проходящие через скутер 1, проходят только через один другой скутер (номер 2).

Главный Судья гонок хочет определить порядок, в котором должны стартовать скутеры, чтобы аварии не произошло. Например, в ситуации, приведенной на рисунке, сначала должен стартовать скутер номер 2 (если попытается стартовать скутер номер 1 или 3, то он столкнется со скутером номер 2). После этого скутеры 1 и 3 могут стартовать в любом порядке (они друг другу не мешают).

Помогите Главному Судье — напишите программу, которая определит какой-нибудь порядок старта скутеров, чтобы аварии не произошло.

Входные данные
В первой строке вводится натуральное число N( 1 ≤ N ≤ 30 000).

В каждой из следующих N строк содержится по 6 чисел: x₁, y₁, x₂, y₂, x₃, y₃ – координаты трех вершин скутера на старте, целые числа, не превосходящие по модулю 10⁶. В начальный момент скутеры не задевают друг друга.

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

Примечание
Первый тест соответствует приведенному рисунку. Ответ 2 3 1 в этом тесте также является правильным
 

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

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

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

Сначала вводится число N — количество отрезков (1≤N≤1000). Далее идет N четверок чисел X_i1, Y_i1, X_i2, Y_i2 задающих координаты концов отрезков. Все эти числа целые, по модулю не превосходящие 10000.

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

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

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

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


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

Далее записано целое число N - количество разрезов (1≤N≤200). Далее описываются сами разрезы. Все разрезы делались вдоль  прямых. Каждая прямая, соответствующая разрезу, задается тремя числами A, B, C такими, что все точки (x,y) этой прямой (и только они) удовлетворяют уравнению Ax+By+C=0 (при этом всегда A2+B2>0).

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

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

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

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

Утверждение гласило: "если взять две карты одной и той же области, сделанные с разным масштабом, и расположить меньшую поверх большей так, что меньшая карта окажется строго внутри большей, то можно найти такую точку (она называется "неподвижная точка"), что то, что изображено в этой точке на обеих картах соответствует одной и той же точке местности". Петя заметил, что пол комнаты можно считать картой комнаты (масштаб 1:1). Он решил найти неподвижную точку для лежащего на полу нарисованного им плана и пола. Но Петя не сумел сделать это самостоятельно, поэтому он обратился к вам за помощью.

Входные данные
Комната Пети и ее план имеют форму прямоугольника. Первая строка содержит два вещественных числа: ширину X и длину Y комнаты Пети (1≤X≤1000, 1≤Y≤1000). Комната расположена в декартовой прямоугольной системе координат так, что углы комнаты расположены в точках с координатами (0,0), (X,0), (X,Y), (0,Y).

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

Все числа заданы с точностью 5 знаков после десятичной точки. План выполнен в масштабе не менее 0.0001 и не более 1. Масштаб не может быть равен 1. Карта расположена лицевой стороной вверх.

Выходные данные
В первую строку выведите 2 вещественных числа — координаты неподвижной точки плана и пола. Ответ нужно выдать с 3 знаками после десятичной точки.

K членов Жюри Десятой Всероссийской олимпиады школьников по информатике решили отметить столь круглую годовщину в одном из лучших ресторанов на Невском проспекте. На десерт вниманию Жюри предложили торт, имеющий форму прямоугольной призмы с выпуклым N-угольником в основании. Жюри вооружается десертными ножами и собирается справедливо разделить торт на K частей равного объема. Ножами можно проводить прямые вертикальные разрезы от одной границы торта до другой; различные разрезы могут иметь общие точки лишь в своих концевых вершинах.

Напишите программу, помогающую членам Жюри построить требуемые K-1 разрезов.

Входные данные
В первой строке входных данных содержатся два целых числа K и N (1 <= K, N <= 50). Далее следуют N пар вещественных чисел - координаты последовательно расположенных вершин N-угольника.

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

Есть две системы координат - первая и вторая. Вторая система устроена так, что ее центр в первой системе имеет координаты (A,B). Ее оси параллельны осям первой системы. При этом точка, которая во второй системе имеет координаты (1,0) в первой имеет координаты (C,B), а точка, имеющая во второй координаты (0,1) - координаты (A,D).

Дана точка, которая в первой системе имеет координаты X1,Y1.
Какие координаты она будет иметь во второй системе?
Какие координаты будет иметь точка в первой системе, если ее координаты во второй - X2, Y2?

Входные данные
Даны вещественные числа A, B, C, D, X1, Y1, X2, Y2.

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

Даны N точек. Требуется построить круг минимального радиуса такой, чтобы этот круг целиком покрывал все точки (допустимо, чтобы некоторые точки лежали на границе круга).

Входные данные
Сначала вводится  число N - количество точек, 3<=N<=100000. Далее идут N пар чисел, задающих координаты точек.  Координаты - вещественные числа.

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

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

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

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

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

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

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

Первые две строки входных данных описывают велосипедные дорожки. Каждая из них содержит по три целых числа – координаты центра окружности, которую представляет собой соответствующая дорожка, и ее радиус. Координаты и радиус не превышают 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}\).