«Кто ходит в гости по утрам, тот поступает мудро…»
Пятачок и Винни-Пух каждое утро ходят пить чай в гости к Кролику. Естественно, самым коротким путем.
К сожалению, однажды Винни-Пуху пришла в голову идея вырыть ловушку для Слонопотама. Самое обидное, что они с Пятачком ее даже вырыли. Поэтому теперь каждое утро, идя в гости к Кролику, они боятся в нее провалиться.
Напишите программу, которая посчитает длину самого короткого безопасного пути от домика Винни-Пуха до домика Кролика.
Ловушка для Слонопотама представляет собой яму абсолютно круглой формы. Путь является безопасным, если он не проходит по ловушке (но может проходить по ее границе).
Во входном файле записаны сначала координаты домика Винни-Пуха XВ YВ, затем — координаты домика Кролика XК YК, а затем — координаты центра и радиус ловушки XЛ YЛ RЛ. Все координаты — целые числа из диапазона от –32000 до 32000. Радиус ловушки — натуральное число, не превышающее 32000.
Домики Винни-Пуха и Кролика не могут находиться внутри ловушки, но могут находиться на ее границе.
Выведите в выходной файл одно число — длину самого короткого безопасного пути от домика Винни-Пуха до домика Кролика с тремя знаками после точки.
0 0 10 0 5 5 1
10.000
3 4 4 4 0 0 5
1.000
Задачи противовоздушной обороны: ...борьба с десантом на всем маршруте пролета,
уничтожение вертолетов огневой поддержки, действующих из засады»
Радиолокационная станция (РЛС) состоит из нескольких передатчиков (не более 5). К сожалению, их нельзя ставить рядом — они друг для друга создают помехи. Каждый передатчик состоит из квадратных модулей, которые располагаются вплотную друг к другу.
Вам дана карта района, в котором расположена РЛС. Вся карта для удобства разбита на квадраты, и для каждого квадрата известно, располагается в нем какой-то из модулей одного из передатчиков РЛС или нет.
Требуется оградить забором (или несколькими заборами) минимально возможной суммарной длины все передатчики РЛС. Забор — это произвольная ломаная (ее элементы не обязаны идти по сторонам клеток). Одним забором могут быть огорожены сразу несколько передатчиков.
Во входном файле записаны два числа N и M, задающие размеры района, в котором расположена РЛС (1N20, 1M20). Далее идет N строк, по M чисел в каждой, задающих карту района. Каждое из этих чисел 0 или 1 — 1 означает, что в этом квадрате находится один из модулей передатчика РЛС, а 0 — что в этом квадрате ничего ценного нет.
Общее количество передатчиков РЛС не превышает 5. Каждый передатчик — это связанная группа модулей (модули называются связанными, если они располагаются в квадратах карты, у которых есть общая граница, либо связаны через какие-то другие модули).
Ограничения на число модулей нет.
В выходной файл выведите одно число — минимально возможную длину забора с тремя значащими цифрами после точки.
2 2 1 0 0 1
6.828
4 5 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1
18.000
Гомотетией с центром O и коэффициентом k 0 называют преобразование плоскости, при котором точка O переходит сама в себя, а любая точка X O – в такую точку Y, что:
Требуется написать программу, которая по координатам вершин двух различных простых N-угольников определяет, существует ли гомотетия, переводящая первый многоугольник во второй и, если существует, вычисляет ее центр и коэффициент.
В первой строке входного файла содержится целое число n (3 ≤ n ≤ 1000) – количество вершин в каждом многоугольнике
В следующих n строках – по два целых числа x и y (-106 ≤ x,y ≤ 106) – координаты вершин первого многоугольника в порядке обхода против часовой стрелки.
В следующих n строках – по два целых числа x и y (-106 ≤ x,y ≤ 106) – координаты вершин второго многоугольника в порядке обхода против часовой стрелки.
Если существует гомотетия, которая переводит первый многоугольник во второй, то необходимо вывести в первой строке выходного файла слово «YES», а во второй строке – три вещественных числа – координаты центра гомотетии и ее коэффициент, которые вычисляются с точностью не менее 10-5. Если искомой гомотетии не существует, необходимо вывести в выходной файл слово «NO».
3 -1 1 1 1 1 5 1 9 -3 1 1 1
YES 1.0 1.0 2.0
3 -1 1 1 1 1 5 1 1 0 0 1 0
NO
Движением плоскости называют такое преобразование плоскости, которое сохраняет попарные расстояния между точками, то есть если A1 и B1 – образы некоторых точек A и B при движении, то |A1B1| = |AB|.
Одной из разновидностей движения плоскости является скользящая симметрия. Скользящей симметрией называют композицию симметрии относительно некоторой прямой l и переноса на вектор, параллельный l (этот вектор может быть нулевым). На рисунке показан пример применения скользящей симметрии к отрезку.
Известно, что любой отрезок можно перевести в любой другой отрезок такой же длины с помощью скользящей симметрии.
Требуется по координатам двух различных точек A и B и двух точек A1 и B1, находящихся на таком же расстоянии друг от друга, как и точки A и B, найти скользящую симметрию, переводящую точку A в точку A1, а точку B в точку B1.
В первой строке входного файла находятся четыре целых числа – координаты двух различных точек A и В. Во второй строке также находятся четыре целых числа – координаты двух различных точек A1 и В1. Гарантируется, что |A1B1| = |AB|. Все числа во входном файле по модулю не превышают 1000. Числа в строках разделены пробелом.
Выведите в выходной файл описание искомой скользящей симметрии, которое представляется в следующем виде.
В первой строке должны выводиться координаты двух различных точек, лежащих на прямой l, относительно которой выполняется симметрия, а во второй – координаты вектора, параллельного этой прямой, на который осуществляется перенос. Вещественные числа должны быть представлены не менее чем с 6 знаками после десятичной точки.
1 1 3 2 -1 1 -3 2
0.000000 0.000000 0.000000 1.000000 0.000000 0.000000
1 1 3 1 3 -1 5 -1
0.000000 0.000000 1.000000 0.000000 2.000000 0.000000
На координатной плоскости расположены равнобедренный прямоугольный треугольник ABC с длиной катета d и точка X. Катеты треугольника лежат на осях координат, а вершины расположены в точках: A (0,0), B (d,0), C (0,d).
Напишите программу, которая определяет взаимное расположение точки X и треугольника. Если точка X расположена внутри или на сторонах треугольника, выведите 0. Если же точка находится вне треугольника, выведите номер ближайшей к ней вершины.
Сначала вводится натуральное число d(не превосходящее 1000), а затем координаты точки X – два целых числа из диапазона от –1000 до 1000.
Если точка лежит внутри, на стороне треугольника или совпадает с одной из вершин, то выведите число 0. Если точка лежит вне треугольника, то выведите номер вершины треугольника, к которой она расположена ближе всего (1 – к вершине A, 2 – к B, 3 – к C). Если точка расположена на одинаковом расстоянии от двух вершин, выведите ту вершину, номер которой меньше.
1. Точка лежит внутри треугольника.
2. Точка лежит вне треугольника и ближе всего к ней вершина A
3. Точка лежит на равном расстоянии от вершин B и C,в этом случае нужно вывести ту вершину, у которой номер меньше, т.е. выведено должно быть число 2
4. Точка лежит на стороне треугольника.
5 1 1
0
3 -1 -1
1
4 4 4
2
4 2 2
0