В точке (0, 0) координатной плоскости расположена лампочка, которая представляет собой точечный источник света. Неподалеку от лампочки находится дом Пети, который представляет собой выпуклый многоугольник с \(N\) вершинами. Сам Петя находится в точке с координатами (\(x\), \(y\)).
Петя хочет увидеть свет. Для этого ему необходимо оказаться в такое точке, что отрезок, соединяющей ее с началом координат, не пересекается с домом Пети (но может его касаться, в частности, проходить вдоль стороны многоугольника дома).
Петя может перемещаться по плоскости со скоростью \(v\). Разумеется, Петя не может проходить сквозь дом (хотя он может двигаться по его границе).
Выясните, какое минимальное время требуется Пете, чтобы оказаться в освещенной точке.
В первой строке вводятся координаты Пети – два неотрицательных вещественных числа, не превышающих 1000, и его скорость v – вещественное число, 10-2\( \le\) v\( \le\) \(10^4\).
Вторая строка содержит \(N\) – число вершин в многоугольнике, задающем Петин дом ( 3\( \le\)N\( \le\)100). Далее в \(N\) строках вводится по два вещественных числа – координаты вершин многоугольника в порядке их обхода против часовой стрелки. Все координаты неотрицательны и не превышают 1000.
Гарантируется, что входные данные корректны, в частности, многоугольник выпуклый, и никакие три его последовательные вершины не лежат на одной прямой. Также гарантируется, что и Петя, и лампочка находятся снаружи от многоугольника, в частности, не находятся на его границе. Расстояние от точки, где находится Петя, до многоугольника и от начала координат до многоугольника не меньше 10-2, расстояние от Пети до начала координат не меньше 10-2.
Выведите минимальное время, за которое Петя сможет попасть в освещенную точку. Ваш ответ должен отличаться от правильного не более чем на 10-4.
3.5 3.5 1.0 4 2.0 0.0 4.0 2.0 2.0 4.0 0.0 2.0
3.58113883008418967000
Триангуляцией некоторого набора точек на плоскости называется набор невырожденных треугольников, удовлетворяющий следующим свойствам:
1) Вершинами треугольников являются только точки исходного набора. Каждая точка исходного набора является вершиной хотя бы одного треугольника.
2) Два различных треугольника либо не имеют общих точек, либо имеют общую вершину, либо имеют общую сторону (но площадь их пересечения всегда равна 0).
3) Любая точка, лежащая внутри выпуклой оболочки исходного набора точек, принадлежит хотя бы одному треугольнику (она может принадлежать нескольким треугольникам, если является их общей вершиной или принадлежит их общей стороне). (Выпуклой оболочкой некоторого набора точек называется наименьший выпуклый многоугольник, содержащий все эти точки).
Триангуляция называется триангуляцией Делоне, если кроме того для нее выполняется следующее условие:
Внутри окружности, описанной около любого треугольника из триангуляции, не лежит ни одна из исходных точек (точки могут лежать на окружности, в частности на ней, очевидно, лежат вершины рассматриваемого треугольника).
Для заданного набора точек найдите количество его триангуляций Делоне (две триангуляции считаются различными, если они отличаются хотя бы одним треугольником).
В первой строке вводится число \(N\) - количество точек (3 <= \(N\) <= 30) исходного набора. Следующие \(N\) строк содержат по одной паре вещественных чисел - координаты соответствующей точки. Никакие три точки не лежат на одной прямой.
Выведите количество различных триангуляций Делоне указанного набора точек.
4 0.0 0.0 1.0 0.0 0.0 1.0 1.0 1.0
2
Множество на плоскости называется выпуклым, если вместе с любыми двумя точками оно содержит также и отрезок, соединяющий эти точки. Минимальное по включению выпуклое множество, содержащее заданное множество точек \(X\), называется выпуклой оболочкой множества \(X\).
В этой задаче вам требуется найти выпуклую оболочку множества точек, принадлежащих заданному набору углов.
Углом называется геометрическая фигура, образованная двумя лучами, выходящими из одной точки. Эта точка называется вершиной угла.
На рисунке слева приведены два угла, на рисунке справа изображена их выпуклая оболочка.
В первой строке вводится число \(n\) - количество углов (1 <= \(n\) <= 1000). Каждая из следующих n строк содержит описание одного угла. Угол задается координатами трех точек: вершины и двух отличных от вершины точек - по одной на каждом из лучей. Все координаты целые и не превышают \(10^4\) по абсолютной величине. Величина угла находится в диапазоне от 0 до 180 градусов, не включительно.
Выведите границу выпуклой оболочки в виде последовательности направленных лучей, прямых и отрезков. Никакие два объекта в выходных данных не должны лежать на одной прямой. Все отрезки должны иметь длину больше нуля. Объекты должны быть перечислены в таком порядке, чтобы начало каждого следующего совпадало с концом предыдущего. Все выводимые числа должны быть целыми и не превосходить \(10^5\) по абсолютной величине. При проходе вдоль описанной границы выпуклая оболочка углов должна быть справа. На первой строке выведите \(L\) - количество объектов в ответе. Следующие \(L\) строк должны содержать описание объектов. Объекты описываются следующим образом:
*Отрезок: "segment \(x_1\) \(y_1\) \(x_2\) \(y_2\)", где (\(x_1\), \(y_1\)) и (\(x_2\), \(y_2\)) - концы отрезка, отрезок считается направленным от (\(x_1\), \(y_1\)) к (\(x_2\), \(y_2\)).
*Луч, направленный от начала: "outray \(x_1\) \(y_1\) \(x_2\) \(y_2\)", где (\(x_1\), \(y_1\)) - начало луча, а (\(x_2\), \(y_2\)) - произвольная точка на луче, отличная от начала.
*Луч, направленный к началу: "inray \(x_1\) \(y_1\) \(x_2\) \(y_2\)", где (\(x_2\), \(y_2\)) - начало луча, а (\(x_1\), \(y_1\)) - произвольная точка на луче, отличная от начала.
*Прямая: "line \(x_1\) \(y_1\) \(x_2\) \(y_2\)", где (\(x_1\), \(y_1\)) и (\(x_2\), \(y_2\)) - две точки на прямой, причем при движении вдоль прямой в ее направлении точка (\(x_1\), \(y_1\)) следует ранее точки (\(x_2\), \(y_2\)).
*Если выпуклой оболочкой является вся плоскость, то выведите \(L\) = 0.
2 3 1 4 1 4 4 2 2 4 3 3 4
3 inray 4 1 3 1 segment 3 1 2 2 outray 2 2 3 5
2 0 0 1 0 0 1 0 0 -1 0 0 1
1 line 0 0 -1 0
2 0 0 1 0 0 1 0 0 -1 0 0 -1
0
Администрация одного института решила построить в холле фонтан. По плану администрации, фонтан должен иметь форму круга с максимально возможным радиусом. Дизайнеру сообщили, что холл института имеет вид прямоугольника, размером \(X\)×\(Y\) метров. Однако когда дизайнер стал выбирать место для фонтана, он столкнулся с серьезной проблемой: в холле института обнаружилось \(N\) круглых колонн, снести которые не представляется возможным.
Таким образом, у него появилась проблема: где следует поместить фонтан, чтобы он имел максимально возможный радиус и не имел ненулевого по площади пересечения с колоннами. Вам предстоит помочь ему в решении этой нелегкой задачи.
В первой строке входных данных содержатся вещественные числа \(X\) и \(Y\), 1 <= \(X\), \(Y\) <= \(10^4\) . Будем считать, что прямоугольник холла расположен на координатной сетке так, что его углы имеют координаты (0, 0), (\(X\), 0), (\(X\), \(Y\)) и (0, \(Y\)).
Во второй строке задается число \(N\) (0 <= \(N\) <= 10) - количество колонн. Следующие \(N\) строк содержат параметры колонн - \(i\)-я строка содержит три вещественных числа \(X_i\), \(Y_i\) и \(R_i\) - координаты центра и радиус \(i\)-й колонны (\(R_i\) <= \(X_i\) <= \(X\)-\(R_i\), \(R_i\) <= \(Y_i\) <= \(Y\)-\(R_i\), 0.1 <= \(R_i\) <= min(\(X\) / 2, \(Y\) / 2); для любых \(i\) ≠ \(j\) sqrt( (\(X_i\) - \(X_j\))2 + (\(Y_i\) - \(Y_j\))2 )>= \(R_i\) + \(R_j\)). Все вводимые числа разделены пробелами.
Выведите три вещественных числа: \(X_F\), \(Y_F\) и \(R_F\) - координаты центра и радиус фонтана. Фонтан должен быть полностью расположен внутри холла (допускается касание стен) и не иметь ненулевого пересечения ни с одной из колонн (допускается касание). Радиус фонтана должен быть максимален. Разделяйте числа пробелами и/или переводами строки. Если решений несколько, выведите любое из них.
10 10 0
5.000 5.000 5.000
1 1000 0
0.500 0.500 0.500
10 10 4 1 1 1 9 9 1 1 9 1 9 1 1
5.000 5.000 4.657
Вася нарисовал на клетчатой бумаге многоугольник, все стороны которого проходят по линиям сетки. После этого в каждой клетке он написал число, равное количеству сторон данной клетки, которые принадлежат сторонам многоугольника. Затем он стер многоугольник так, что остался листок бумаги, в каждой клетке которого написано число.
Восстановите нарисованный Васей многоугольник.
В первой строке входных данных содержатся два натуральных числа: \(Y\) - количество строк и \(X\) - количество столбцов листа (3 <= \(Y\) <= 1000, 3 <= \(X\) <= 1000). В каждой из следующих \(Y\) строк задается по \(X\) целых неотрицательных чисел, не превосходящих 4. Ни одна из сторон многоугольника не проходит по границе листа бумаги.
Выведите искомый многоугольник в следующем формате.
Выходные данные должны содержать \(Y\) строк по 2\(X\)-1 символов в каждой (по одному символу на клетку и линию между клетками).
В первой строке выведите вертикальные отрезки в верхнем ряду клеток, обозначая их символом | (вертикальная черта - символ с кодом 124) и горизонтальные отрезки, отделяющие первый ряд клеток от следующего, обозначая их символом _ (подчеркивание). Если соответствующий отрезок в данном многоугольнике отсутствует, выведите вместо него символ . (точка). Во второй строке выведите в том же формате вертикальные отрезки во втором ряду и горизонтальные отрезки, отделяющие второй ряд от третьего. И т.д. В каждой строке на нечетных местах могут стоять только символы точка или подчеркивание, на четных местах - символы точка или вертикальная черта.
Гарантируется, что хотя бы одно решение существует. Если решений несколько, выведите любое из них.
4 4 0 0 1 0 0 2 3 1 1 3 2 1 0 1 1 0
...._.. .._|.|. .|_._|. .......