Страница: 1 Отображать по:
Даны две пересекающихся окружности. Необходимо найти кратчайший путь от точки до точки по окружностям.

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

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

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

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

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

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

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

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

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

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

includegraphics{pics/bike.1} includegraphics{pics/bike.2} includegraphics{pics/bike.3}
Примеры
Входные данные
0 0 5
4 0 3
3.0 4.0
1.878679656440357 -2.121320343559643
Выходные данные
8.4875540166
Входные данные
0 0 5
4 0 3
4.0 3.0
4.0 -3.0
Выходные данные
6.4350110879
Входные данные
0 0 4
10 0 4
4.0 0.0
6.0 0.0
Выходные данные
-1
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
В неориентированном графе, где для ребра указана его стоимость, мы владеем некоторым набором ребер. Необходимо купить все дороги по маршруту и продать часть своих дорог.

В одном феодальном государстве средневековой Европы было n городов и m дорог, каждая из которых соединяла некоторые два города. Каждая дорога принадлежала правителю одного из городов (не обязательно одного из тех, которые она соединяла). Однажды правитель города S решил объявить войну правителю города T. Перед ним сразу же встала нелегкая задача: как довести армию до города T.

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

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

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

В первой строке вводятся целые числа n и m – количество городов и дорог соответственно ( 2$ le$n$ le$2 000, 1$ le$m$ le$50 000). Города нумеруются от 1 до n, города S и T имеют номера 1 и n соответственно.

Следующие n строк содержат под одному целому числу ri – плату за проезд через город i ( 0$ le$ri$ le$10 000, r1 = rn = 0).

Далее идут m строк,  задающих описания дорог. Дорога описывается четырьмя целыми числами: ai, bi, pi и ci. Здесь ai и bi – номера городов, которые соединяет дорога, pi – номер города, правителю которого она принадлежит, ci – ее стоимость ( ai$ ne$bi, 1$ le$ci$ le$10 000). По дороге можно перемещаться в обоих направлениях. Любые два города соединены не более, чем одной дорогой.

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

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

Если решения нет, выведите  число -1.

Примеры
Входные данные
3 3
0
1
0
1 2 1 10
2 3 1 10
3 1 2 2
Выходные данные
2 1 2
1 3
1 3
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Дан точечный источник света и многоугольник. Необходимо пройти от заданной точки до ближайшей освещенной точки, не проходя через дом.

В точке (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
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.

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

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

Во входном файле записаны сначала числа N ($2 \le N \le 100$) и E ($2 \le E \le N$). Затем записано число M ($0 \le M \le 100$), обозначающее число рейсов электричек. Далее идет описание M рейсов электричек. Описание каждого рейса электрички начинается с числа Ki ($2 \le K \le N$) — количества станций, на которых она останавливается, а далее следует Ki пар чисел, первое число каждой пары задает номер станции, второе — время, когда электричка останавливается на этой станции (время выражается целым числом из диапазона от 0 до 109). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.

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

В выходной файл выведите одно число — минимальное время, когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они добраться не смогут, выведите –1.

Примеры
Входные данные
5 2
2
4 1 1 3 2 4 10 5 20
3 5 10 4 15 2 40
Выходные данные
40

Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест